### 技术控

今日:46| 主题:57640

# [其他] Check If Given Array Can be Arranged In Left or Right Positioned Array

122 3
 Given an array arr[] of size n>4, the task is to check whether the given array can be      arrangedin the form of Left or Right positioned array?              Left or Right Positioned Arraymeans each element in the array is equal to the number of elements to its left or number of elements to its right.        Examples: Input  : arr[] = {1, 3, 3, 2} Output : "YES"   This array has one such arrangement {3, 1, 2, 3}. In this arrangement, first element '3' indicates that three numbers are after it, the 2nd element '1' indicates that one number is before it, the 3rd element '2' indicates that two elements are before it. Input : arr[] = {1, 6, 5, 4, 3, 2, 1} Output: "NO" // No such arrangement is possible Input : arr[] = {2, 0, 1, 3} Output: "YES" // Possible arrangement is {0, 1, 2, 3} Input : arr[] = {2, 1, 5, 2, 1, 5} Output: "YES" // Possible arrangement is {5, 1, 2, 2, 1, 5}复制代码 A    simple solutionis to generate all possible arrangements (seethis article) and check for the Left or Right Positioned Array condition, if each element in the array satisfies the condition then “YES” else “NO”. Time complexity for this approach is O(n*n! + n), n*n! to generate all arrangements and n for checking the condition using temporary array.     An    efficient solutionfor this problem needs little bit observation and pen-paper work. To satisfy the Left or Right Positioned Array condition all the numbers in the array should either be equal to index, i or (n-1-i) and arr < n. So we create an visited[] array of size n and initialize its element with 0. Then we traverse array and follow given steps :          If visited[arr] = 0 then make it 1, which checks for the condition that number of elements on the left side of array arr[0]…arr[i-1] is equal to arr.    Else make visited[n-arr-1] = 1, which checks for the condition that number of elements on the right side of array arr[i+1]…arr[n-1] is equal to arr.    Now traverse visited[] array and if all the elements of visited[] array become 1 that means arrangement is possible “YES” else “NO”.   // C++ program to check if an array can be arranged // to left or right positioned array. #include using namespace std; // Function to check Left or Right Positioned // Array. // arr[] is array of n elements // visited[] is boolean array of size n bool leftRight(int arr[],int n) {     // Initially no element is placed at any position     int visited[n] = {0};     // Traverse each element of array     for (int i=0; i

xdagl 投递于 2016-10-18 10:01:28
 我小学十年,中学十二年,我被评为全校最熟悉的面孔,新老师来了都跟我打听学校内幕……

 元芳你怎么看？

meitime 投递于 2016-10-25 10:53:42
 有谁会在时过境迁之后还在那里等你。

• ## 买 Supreme ，越来越像买奢侈品…

微信号 nowre_offic [...]

• ## 为移动头显提供追踪方案，Antilatency融资2

一家专注于位置追踪解决方案的初创公司Antilaten [...]

• ## 注意：淘宝内容营销6月份是个分水岭

最近，天猫APP升级了，更加精简与个性化了。 据 [...]

• ## 真正吃到饱! 小米“米粉卡”来了: 3元/天省

今天除了小米Max2要发布，小米还憋有大招，无限 [...]

• ## 关中国什么事？越南和印尼在南海冲突干起来

微信号 zouyinni 微 [...]

• ## 女人过了25+的年龄，千万别这样穿！超令男

微信号 dapei55 也 [...]

• ## 研究表明Apple Watch心率追踪方面最准

威锋网讯，日前来自斯坦福大学的一项新研究深入 [...]

• ## 大疆的小魔法 Spark 无人机，除了装进口袋

你在遛狗，你突然想记录下这段美好的画面， [...]

• ## 用panda.tv 融资10亿的熊猫直播怼得过BAT吗

易名中国（eName.cn）5月25日讯，“直播大战”一 [...]

• ## 贵阳市联合阿里云启动块数据中心云平台建设

接到报警后，指令直接发送到距离最近民警的手持 [...]