blocks|key|4170666|text|此外，您可以在没有过滤的情况下使用相同的代码，但在某些情况下效率较低。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4170667|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);
}|code-block|syntax|javascript|4170668|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Futhermore, you can use the same code without filtering, but in some cases the effective are less.

<pre><code>function solution(A) {
 let array = [...Array(1000001).keys()];

 A.forEach(a =&gt; {
 if(array[a] != null)
 array[a] = null;
 });
 array[0] = null;

 return array.findIndex(e =&gt; e != null);
}
</code></pre>

blocks|key|4170114|text|另一种方法可能是对数组进行排序并搜索第一个间隙：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4170115|function+solution(arr)+{
++arr.sort((a,+b)+=>+a+-+b);
++for(var+i+=+1;+i+<+arr.length;+i%2B%2B)+{
++++if(arr[i]+>=+0+&&+arr[i]+-+arr[i+-+1]+<=+1)+
+++++++return+arr[i+-+1]+%2B+1;
++}
++return+arr[i+-+1]+%2B+1;
}|code-block|syntax|javascript|4170116|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Another approach might be to sort the array and search for the first gap:

<pre><code>function solution(arr) {
 arr.sort((a, b) =&gt; a - b);
 for(var i = 1; i &lt; arr.length; i++) {
 if(arr[i] &gt;= 0 &amp;&amp; arr[i] - arr[i - 1] &lt;= 1) 
 return arr[i - 1] + 1;
 }
 return arr[i - 1] + 1;
}
</code></pre>

blocks|key|4170241|text|另一种处理唯一积极的事情的方法。我的JS解决方案得到了100分。基本上，我生成一个新数组，它的键将是原始数组的值，并将每个数组设置为某个真值。这做了两件事:它从新数组的迭代循环中取出负值，还允许您从最小的值开始向上循环，并返回给您未定义的第一个索引。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4170242|function+solution(A)+{
++++orderedArr+=+[];
++++for+(let+i+=+0;+i+<+A.length;+i%2B%2B)+{
++++++++if+(!orderedArr[A[i]])+{
++++++++++++orderedArr[A[i]]+=+true;
+++++++++}
++++}
++++if+(orderedArr.length+===+0)+return+1;
++++for+(let+i+=+1;+i+<+orderedArr.length;+i%2B%2B)+{
++++++++if+(!orderedArr[i])+{
++++++++++++return+i;
++++++++}
++++}
++++return+orderedArr.length;
}|code-block|syntax|javascript|4170243|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Another way to deal with the positive only thing. My JS solution got 100 across the board. Basically, I generate a new array whose keys will be the values of the original array and set each to some truthy value. This does two things: it takes the negative values out of the iteration loop of the new array, and also allows you to loop from the smallest value up and return the first index that gives you undefined.

<pre><code>function solution(A) {
 orderedArr = [];
 for (let i = 0; i &lt; A.length; i++) {
 if (!orderedArr[A[i]]) {
 orderedArr[A[i]] = true;
 }
 }
 if (orderedArr.length === 0) return 1;
 for (let i = 1; i &lt; orderedArr.length; i++) {
 if (!orderedArr[i]) {
 return i;
 }
 }
 return orderedArr.length;
}
</code></pre>

blocks|key|4170879|text|这是Java+8版本的解决方案，提交后的结果是100%25。我使用HashSet来消除重复的元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4170880|import+java.util.*;|code-block|syntax|javascript|4170881|类解决方案{|4170882|公共int解决方案(int[]+A)+{|4170883|++++//+sort+the+array
++++Arrays.sort(A);
++++int+len+=+A.length;

++++int+result+=+1;

++++if+(len+==+0)+{
++++++++result+=+1;
++++}else+{
++++++++//+populate+hashset+from+the+array+to+eliminate+duplicate
++++++++HashSet<Integer>+aSet+=+new+HashSet<Integer>();
++++++++for(int+i=0;+i<len;+i%2B%2B)+{
++++++++++++aSet.add(A[i]);
++++++++}

++++++++//+now+loop+through+from+1+to+len+in+the+array+and+check+if+index+exists
++++++++for(int+j=1;+j<len%2B1;j%2B%2B)+{
++++++++++++boolean+exists+=+aSet.contains(j);
++++++++++++if(!exists)+{
++++++++++++++++result+=+j;
++++++++++++++++break;
++++++++++++}else+{
++++++++++++++++if(j>0)+{
++++++++++++++++++++result+=+j%2B1;
++++++++++++++++}
++++++++++++}
++++++++}
++++}

++++return+result;

}|4170884|}|4170885|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|T|8|@]|9|@]|A|$]]|$1|K|3|L|5|D|7|U|8|@]|9|@]|A|$E|F]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Here is the Java 8 version of the solution which resulted in 100% after submission. I used HashSet to eliminate the duplicate element.

<pre><code>import java.util.*;
</code></pre>

class Solution {

public int solution(int[] A) {

<pre><code> // sort the array
 Arrays.sort(A);
 int len = A.length;

 int result = 1;

 if (len == 0) {
 result = 1;
 }else {
 // populate hashset from the array to eliminate duplicate
 HashSet&lt;Integer&gt; aSet = new HashSet&lt;Integer&gt;();
 for(int i=0; i&lt;len; i++) {
 aSet.add(A[i]);
 }

 // now loop through from 1 to len in the array and check if index exists
 for(int j=1; j&lt;len+1;j++) {
 boolean exists = aSet.contains(j);
 if(!exists) {
 result = j;
 break;
 }else {
 if(j&gt;0) {
 result = j+1;
 }
 }
 }
 }

 return result;

}
</code></pre>

}

blocks|key|4170925|text|O(n)解决方案javascript。使用两个循环。第一个循环将所有大于0的元素放入map/object第二个循环中，检查map中是否存在值。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4170926|function+solution(A)+{
++++let+obj+=+{};
++++let+min+=+1;

+++//iterate+over+all+items+in+the+array+and+store+the+value+in+a+object;
++++for+(let+i+=+0,+len=A.length;+i+<+len;+i%2B%2B)+{
++++++++const+num+=+A[i];
++++++++if+(num+>+0)+{
++++++++++++obj[num]+=+true;
++++++++}
++++}
++++//start+with+min===1+check+if+it's+in+the+object
++++//+if+it+is+if+it's+in+the+object+then+increment+min+and+repeat+until+min+not+in+object.
++++while+(obj[min])+{
++++++++min%2B%2B;
++++}
++++//this+will+return+the+smallest+value+not+in+array+bigger+or+equal+to+1
++++return+min;
}|code-block|syntax|javascript|4170927|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

O(n) solution javascript.
using two loops. 
first loop puts all elements bigger then 0 into a map/object
second loop check if value existing in map. 

<pre><code>function solution(A) {
 let obj = {};
 let min = 1;

 //iterate over all items in the array and store the value in a object;
 for (let i = 0, len=A.length; i &lt; len; i++) {
 const num = A[i];
 if (num &gt; 0) {
 obj[num] = true;
 }
 }
 //start with min===1 check if it's in the object
 // if it is if it's in the object then increment min and repeat until min not in object.
 while (obj[min]) {
 min++;
 }
 //this will return the smallest value not in array bigger or equal to 1
 return min;
}
</code></pre>

blocks|key|4170391|text|​|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4170392|📷|atomic|offset|length|4170393|4170394|function+solution(A)+{
++++const+numbers+=+[]

++++for+(let+i+=+0;+i+<+A.length;+i%2B%2B)+{
++++++++numbers[A[i]]+=+true
++++}

++++if+(numbers.length+===+0)+{
++++++++return+1+++
++++}

++++for+(let+i+=+1;+i+<+numbers.length;+i%2B%2B)+{
++++++++if(numbers[i]+===+undefined)+{
++++++++++++return+i
++++++++}
++++}

++++return+numbers.length
}|code-block|syntax|javascript|4170395|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/092c207aeffb9cc389e75ba9fa5c88ef.png|imageAlt^0|0|0|1|0|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|W|8|@]|9|@$E|X|F|Y|1|Z]]|A|$]]|$1|G|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|11|8|@]|9|@]|A|$K|L]]|$1|M|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|N|$O|$5|P|Q|R|A|$S|T|U|-4]]]]

<a href="https://i.stack.imgur.com/z9siw.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/z9siw.png" alt="enter image description here"></a>

<pre><code>function solution(A) {
 const numbers = []

 for (let i = 0; i &lt; A.length; i++) {
 numbers[A[i]] = true
 }

 if (numbers.length === 0) {
 return 1 
 }

 for (let i = 1; i &lt; numbers.length; i++) {
 if(numbers[i] === undefined) {
 return i
 }
 }

 return numbers.length
}
</code></pre>

blocks|key|4171007|text|这是我的100%25性能解决方案|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4171008|function+solution(A)+{
++++let+missingInteger+=+1;
++++A+=+A.sort((a,+b)+=>+a+-+b);
++++for(let+i+=+0;+i+<+A.length;+i%2B%2B){
++++++++if(A[i]+==+missingInteger+)+missingInteger%2B%2B;
++++++++if(A[i]+>+missingInteger)+return+missingInteger;
++++}
++++return+missingInteger;
}|code-block|syntax|javascript|4171009|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is my 100% performant solution
<pre><code>function solution(A) {
 let missingInteger = 1;
 A = A.sort((a, b) =&gt; a - b);
 for(let i = 0; i &lt; A.length; i++){
 if(A[i] == missingInteger ) missingInteger++;
 if(A[i] &gt; missingInteger) return missingInteger;
 }
 return missingInteger;
}
</code></pre>

blocks|key|4171023|text|这是我的解决方案，我得了100分|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4171024|function+missingInteger(a)+{
const+map+=+{};

let+largest;
for+(let+i+=+0;+i+<+a.length;+i%2B%2B)+{
++++const+number+=+a[i];

++++if+(number+<=+0)+{
++++++++continue;
++++}

++++if+(!largest+%7C%7C+number+>+largest)+{
++++++++largest+=+number;
++++}

++++map[number]+=+number;
}

if+(!largest)+{
++++return+1;
}

let+exists+=+true;
let+i;
for+(i+=+1;+i+<=+largest;+i%2B%2B)+{
++++if+(map[i])+{
++++++++continue;
++++}

++++exists+=+false;
++++break;
}

if+(!exists)+{
++++return+i;
}

return+largest+%2B+1;
}|code-block|syntax|javascript|4171025|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is my solution and I got 100% score
<pre><code>function missingInteger(a) {
const map = {};

let largest;
for (let i = 0; i &lt; a.length; i++) {
 const number = a[i];

 if (number &lt;= 0) {
 continue;
 }

 if (!largest || number &gt; largest) {
 largest = number;
 }

 map[number] = number;
}

if (!largest) {
 return 1;
}

let exists = true;
let i;
for (i = 1; i &lt;= largest; i++) {
 if (map[i]) {
 continue;
 }

 exists = false;
 break;
}

if (!exists) {
 return i;
}

return largest + 1;
}
</code></pre>

This afternoon I try to resolve the demo test of Codility. After thinking a lot how to increase the performance (and searching a little bit), I created this code:

<pre><code>function solution(A) {
 let array = [...Array(1000001).keys()];

 const onlyPositives = A.filter(n =&gt; n&gt;0);
 if(onlyPositives.length == 0) return 1

 onlyPositives.forEach(a =&gt; {
 if(array[a] != null)
 array[a] = null;
 });
 array[0] = null;

 return array.findIndex(e =&gt; e != null);
}
</code></pre>

Anyone have another Idea?

Codility MissingInteger Javascript solution (proposal)

Java

今天下午，我试着解决Codility的演示测试。在思考了很多如何提高性能(并进行了一点搜索)之后，我创建了以下代码：function solution(A) {    let array = [...Array(1000001).keys()];    const onlyPositives = A.filter(n ...

问Codility MissingInteger Javascript解决方案(建议书)
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Codility MissingInteger Javascript解决方案(建议书)EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Codility MissingInteger Javascript解决方案(建议书)
EN