缺少整数编码 Javascript
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/30724992/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
missing integer codility Javascript
提问by Firstname Lastname
Write a function:
function solution(A);that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer (greater than 0) that does not occur in A. For example, given:
A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2the function should return 5. Assume that:
? N is an integer within the range [1..100,000]; ? each element of array A is an integer within the range[?2,147,483,648..2,147,483,647].
Complexity:? expected worst-case time complexity is O(N); ? expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
写一个函数：
function solution(A);给定一个由 N 个整数组成的非空零索引数组 A，返回 A 中不出现的最小正整数（大于 0）。例如，给定：
A[0] = 1 A[1] = 3 A[2] = 6 A[3] = 4 A[4] = 1 A[5] = 2该函数应返回 5。假设：
? N is an integer within the range [1..100,000]; ? each element of array A is an integer within the range[?2,147,483,648..2,147,483,647]。
复杂度：? 预期的最坏情况时间复杂度为 O(N)；? 预期的最坏情况空间复杂度为 O(N)，超出输入存储（不包括输入参数所需的存储）。
My Answer is 100% WRONG! What is wrong with it? First let me state the obvious errors
我的答案是 100% 错误的！它有什么问题？首先让我说明明显的错误
- return value - i return 0, because there is no indication of what to return, if there is no missing integer.
- 返回值 - 我返回 0，因为没有指示返回什么，如果没有丢失的整数。
Assumptions I made that may be wrong
我所做的假设可能是错误的
- returns the minimal positive integer (greater than 0) that does not occur in A. Here I do not check for negative values
- 返回 A 中不出现的最小正整数（大于 0）。这里我不检查负值
my code, which works on own test cases, and works on negative numbers too, got 0%.
我的代码适用于自己的测试用例，也适用于负数，结果为 0%。
function solution(A) {
// write your code in JavaScript (Node.js 0.12)
A.sort();
var a_length = A.length;
for(var i = 0; i < a_length; i++){
// if i is 0 - 1 = -1 then do not do the following
// if i is 1 - 1 - 0 then do the follow
// if i >= 0 then do the following
if(i - 1 >= 0){
// remember above there is a A.sort() so it
// looks like this
// A[0] = 1
// A[1] = 1
// A[2] = 2
// A[3] = 3
// A[4] = 4
// A[5] = 6
// if A[1] is 1 and A[1-1 = 0] is 1 then this is 1>1 false
// if A[2] is 2 and A[2-1 = 1] is 1 then this is 1>1 false
// if A[3] is 3 and A[3-1 = 2] is 2 then this is 1>1 false
// if A[4] is 4 and A[4-1 = 3] is 3 then this is 1>1 false
// if A[5] is 6 and A[5-1 = 4] is 4 then this is 2>1 true return A[i - 1] + 1 where A[5 - 1 = 4] is 4 + 1 is 5. 5 is returned.
if(A[i] - A[i - 1] > 1){
return A[i - 1] + 1;
}
}
}
// this does not check for negative
// returns the minimal positive integer (greater than 0
// this is a return no minimal positive integer found
return 0;
}
Everything is wrong, example test result:
一切都错了，示例测试结果：
simple simple test 0.072?s WRONG ANSWER got 3 expected 1
simple simple test 0.072?s WRONG ANSWER got 3 expected 1
Why does it work for me and not for them.
为什么它对我有用而不对他们有用。
回答by Jose Douglas Ramirez Espitia
function solution(A) {
var min = 1;
A.sort(function(a,b){
// Sort the array explicit way
return a - b;
});
for (var i in A) {
if (A[i] > -1 && A[i] == min) {
min++;
}
}
return min;
}
回答by Nikola Ravic
There is my solution with JavaScript for Codility MissingInteger (got 100/100)
有我的 Codility MissingInteger 的 JavaScript 解决方案（得到 100/100）
function solution(A) {
const len = A.length;
const hash = {};
for (let i = 0; i < len; i++) {
// here we are making an object with all
// numbers in a given array as object keys and values
// if 0 is given as possible digit we could assing
// hash[A[i]] = true; or any truthy value
hash[A[i]] = A[i];
}
for (let i = 1; i < 1000002; i++) {
// here we are trying to find any number
// between 1 and 1000001 (given constraints)
// which do not exists in an object
// if the number is not in the object that's our missing one
if(!hash[i]) return i;
}
return 1;
}
回答by ben_flock
For this problem I like to start by sorting the given array. I then iterate through the sorted array with a reduce. I give the reduce an accumulator accinitially equal to 1(that's what the 1 after the comma is for). Only when the element valis equal to the accumulator do I increment the accumulator. Otherwise, I return the accumulator as is. When I can no longer find an element in the array equal to the accumulator, that accumulator is the lowest missing positive integer.
对于这个问题，我喜欢从对给定数组进行排序开始。然后我用一个reduce 遍历排序后的数组。我给 reduce 一个累加器acc最初等于1（这就是逗号后面的 1 的含义）。只有当元素val等于累加器时，我才会增加累加器。否则，我将按原样返回累加器。当我无法再在数组中找到等于累加器的元素时，该累加器是最小的缺失正整数。
const solution = A => {
A.sort((a, b) => a - b);
return A.reduce((acc, val) => acc === val ? acc + 1 : acc, 1);
}
I know this question's been around for a while but I hope this answer is useful for someone. I use Array.prototype.sort(), Array.prototype.reduce(), and a ternaryin this answer. A knowledge of those patterns should give more insight into this answer.
我知道这个问题已经存在一段时间了，但我希望这个答案对某人有用。我在这个答案中使用了Array.prototype.sort()、Array.prototype.reduce()和一个三元组。了解这些模式应该可以更深入地了解这个答案。
回答by Kaflan Katrusha
function solution(A) {
A.sort(function(a,b){
// Sort the array explicit way
return a - b;
});
return A.reduce((prev, next)=> {
if(next > -1 && next === prev) {
prev++;
}
return prev;
}, 1);
;
}回答by Nick
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.
我的 JS 解决方案得到了 100。基本上，我生成一个新数组，其键将是原始数组的值，并将每个数组设置为某个真实值。这做了两件事：它从新数组的迭代循环中取出负值，并且还允许您从最小值向上循环并返回第一个给您未定义的索引。
function solution(A) {
orderedArr = [];
for (let i = 0; i < A.length; i++) {
if (!orderedArr[A[i]]) {
orderedArr[A[i]] = true;
}
}
if (orderedArr.length === 0) return 1;
for (let i = 1; i < orderedArr.length; i++) {
if (!orderedArr[i]) {
return i;
}
}
return orderedArr.length;
}
回答by kevin.t
function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
var b = A.sort(function(a,b){return a-b});
var length = b.length;
var min = b[0];
var max = b[length-1];
if (max<=0){return 1;}
if (min<=0 && max==1){return 2;}
if (min>1){return 1;}
if (min >=0){
for(var i=0; i<length; i++){
if(b[i+1]- b[i] > 1){
return b[i]+1;
}
}
}
if (min<=0 && max>=0){
for(var i=0; i<length; i++){
if(b[i]>0 && b[i-1]<=0){
if(b[i]-0>1){
return 1;
}
if(b[i+1]-b[i]>1){
return b[i]+1;
}
}
if(b[i]>0){
if(b[i+1]- b[i] > 1){
return b[i]+1;
}
}
}
}
return max+1;
}
}
回答by Shanks
My solution:
我的解决方案：
function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
var B = A.sort(function(a,b){return a-b});
if(A.length == 1) {
if(A[0] > 0) {
if(A[0]>1) {
return 1
} else {
return A[0]+ 1;
}
} else {
return 1
}
} else if(A.length > 1) {
let max = Math.max.apply(null,A);
let min = Math.min.apply(null,A);
if(max > 0) {
if(B[0]-0 > 1) { //for arrays that have a minimum higher than 1
return 1
}
for(i=0;i<B.length-1;i++) {
if(B[i+1]- B[i] > 1){ //check the difference between next and current number, we also ignore the case of [x,-1,1,x2], since if a 0 is omitted, 1-(-1) will make 0 the highest missing number
if(B[i] == -1 && B[i+1] == 1) {
//do nothing
} else {
if(B[i]>0) {
return B[i]+1; //if the first number is positive, we can say the number after it is the smallest possible integer
} else {
return 1
}
}
}
}
return max + 1;
} else {
return 1
}
} else {
return null;
}
}
回答by Rengare
Task score: 100% Correctness: 100% Performance: 100 %
任务得分：100% 正确性：100% 性能：100%
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
let map = {};
A.map(x => { map[x] = x; return x });
let result = 1;
while (true) {
if (!map[result]) return result;
result++;
};
}
回答by user2983165
try the following,
尝试以下，
let expecterNumber = 1;
A.sort(function(a,b){
return a - b;
});
for (let i in A) {
if (A[i] <= 0 || A[i] == A[i - 1]) continue
if (A[i] != expecterNumber) break
expecterNumber++;
}
return expecterNumber;
}
回答by AbdurrahmanY
For JavaScript try following. Test score 100/100
对于 JavaScript，请尝试以下操作。测试分数 100/100
Detected time complexity: O(N) or O(N * log(N))
检测时间复杂度：O(N) 或 O(N * log(N))
function solution(A) {
var missingInt = 1;
A.sort((a, b) => { return a - b; });
for (var i = 0; i < A.length; i++) {
if (A[i] >= (missingInt + 1)) {
break;
}
if (A[i] == missingInt) {
missingInt++;
}
}
return missingInt++;
}
