javascript - codility MissingInteger Javascript解决方案(建议)

今天下午我尝试解决Codility的演示测试,在考虑了很多如何提高性能(再搜索一下)之后,我创建了以下代码:


function solution(A) {


 let array = [...Array(1000001).keys()];



 const onlyPositives = A.filter(n => n>0);


 if(onlyPositives.length == 0) return 1



 onlyPositives.forEach(a => {


 if(array[a] != null)


 array[a] = null;


 });


 array[0] = null;



 return array.findIndex(e => e != null);


}



有谁知道?

时间:

此外,你可以不用过滤而且使用相同的代码,但是,在某些情况下,有效。


function solution(A) {


 let array = [...Array(1000001).keys()];



 A.forEach(a => {


 if(array[a] != null)


 array[a] = null;


 });


 array[0] = null;



 return array.findIndex(e => e != null);


}



另一种方法是对数组进行排序,并搜索第一个间隙:


function solution(arr) {


 arr.sort((a, b) => a - b);


 for(var i = 1; i < arr.length; i++) {


 if(arr[i] >= 0 && arr[i] - arr[i - 1] <= 1) 


 return arr[i - 1] + 1;


 }


 return arr[i - 1] + 1;


}



问题

编写函数:int解决方案(NSMutableArray *A);

如果给定一个数组的N个整数,则返回没有出现在中的最小正整数(大于0 )。

例如,


Given A = [1, 3, 6, 4, 1, 2], the function should return 5.


Given A = [1, 2, 3], the function should return 4.


Given A = [−1, −3], the function should return 1.



为以下假设编写一个有效的算法:

N是[1..100 ,000]范围内的整数; 数组A的每个元素都是[−1 ,000 ,000..1 ,000 ,000]范围内的一个整数。

objective-c解决方案O(n)

由Codility给出的结果

任务分数:100%
正确:100%
性能:100%

时间复杂度

最糟糕的时间复杂度是O(n)或O(N *log(N))

Xcode Solution Here


+(int)solution:(NSMutableArray*)array {



 /******** Algorithm Explanation ********/


 // STEP 1


 // Check for edge cases - when the array is empty [], we should return 1


 // STEP 2


 // Generate NSSet from the Array in oder to eliminate possible duplicates


 // STEP 3


 // Implement a loop taking in consideration:


 // N always starts from 1 and so on (1,2,3...n)


 // There is always one missing element in the array


 // So, in the Array we sould have N => (1,2,3...n+1)


 //


 // STEP 4


 // Look for the current element in the SET


 // If the element does't exist, that means we have found the smallest one missing element.


 // Break the loop.



 // STEP 1


 int smallestCandidate = 0;


 int n = (int)[array count];


 if (n==0) {


 smallestCandidate = 1;


 }


 else {


 // STEP 2


 NSSet *elements = [NSSet setWithArray:array];



 // STEP 3


 for (int i=1; i<=(n+1); i++) {


 BOOL exist = [elements containsObject:@(i)];


 if(!exist) {


 // STEP 4


 smallestCandidate = i;


 return smallestCandidate;


 }


 }


 }


 return smallestCandidate;


}



...