javascript 不在数组中出现的最小正整数

wj8zmpe1  于 2023-04-19  发布在  Java
关注(0)|答案(2)|浏览(125)

我正在使用javascript尝试this question。当我在网站上运行我的实现时,我得到了11%,这不包括糟糕的运行时状态,我失败了四个隐藏的测试。
我不明白我的实现是如何失败的。我知道这不是一个伟大的实现,在链接的问题中有更清晰的工作答案,但我仍然很好奇 * 我使用了什么错误的逻辑 *。

A = A.filter(a => a > 0).sort()

  if (A.length === 0) {
    return 1
  }
  
  if (A.length === 1) {
    return A[0] + 1
  }

  for (let i = 0; i < A.length; i++) {
    let curr = A[i]
    let next = A[i + 1]

    if (curr !== next && (curr + 1) !== next) {
      return curr + 1
    }
  }

我的逻辑是,因为我正在从最低到最高遍历一个正整数的有序数组,如果当前元素+ 1不等于后面的元素(即[5,7]将是5 + 1!= 7),则存在一个间隙,这是缺失的整数。
如果循环一直到最后,最后一个if语句仍然会被触发,因为next是undefined,它将返回max值+ 1。

bqujaahr

bqujaahr1#

不用对数组进行排序,只需查找数组的最大值并在函数中使用它。注意,不用处理数组,可以使用set。set .has方法比include方法快。

function  smallest_positive(ar){
    let set = new Set(ar)
    let mx = Math.max(...set);
    for(let i = 1; i < mx; i++) 
        if(!set.has(i)) return i;
    return mx < 1 ? 1: mx + 1;
}; 

console.log(smallest_positive([-1,4,2,-3]))
console.log(smallest_positive([1, 2, 3]))
console.log(smallest_positive([5,7]))
console.log(smallest_positive([1, 3, 6, 4, 1, 2]))
iklwldmw

iklwldmw2#

这个解决方案并不是最有效的,但是这个过程在一个逐步的大纲中进行了解释,这应该可以帮助你看到OP失败的地方(特别是缺少一个正确的.sort()数字的函数)。

  • 首先,数组必须仅由正整数组成。
  • 将数组转换为Set以消除任何重复的数字。
let A = new Set(array)
  • Set转换回带有括号和spread运算符的数组。
A = [...new Set(array)]
  • .sort()通过在每次迭代中使用a - b函数以升序对数组进行数字化。
A = [...new Set(array.sort((a, b) => a - b))]
  • .filter()数组,以便只保留大于0的数字。
A = [...new Set(array.sort((x, y) => x - y))].filter(n => n > 0);
  • 接下来,如果数组没有1,则添加一个简单的控制语句来短路函数。
    • 如果数组的第一个数字不是1,则返回1*。
if (A[0] !== 1) {
  return 1;
}
  • 然后使用.flatMap()遍历数组,通过三元条件运算符返回数组序列中缺失的正整数。
A = A.flatMap((n, i, a) => /* ternary conditional operators */);
  • 第一个条件:* 如果下一个数字:a[i + 1]大于当前数字+1:n + 1 ...*
A = A.flatMap((n, i, a) => a[i + 1] > n + 1)
  • 第二个条件:||,如果下一个数字:a[i + 1]undefined ...
/*...truncated*/ a[i + 1] > n + 1 || a[i + 1] === undefined)
    • 返回n + 1否则返回空数组(将被.flatMap()展平为空)*
/*...truncated*/ a[i + 1] > n + 1 || a[i + 1] === undefined ? n + 1 : [])
  • 最后,返回数组的第一个数字。
return A[0];
function xInt(array) {
  let A = [...new Set(array.sort((a, b) => a - b))].filter(n => n > 0);
  if (A[0] !== 1) {
    return 1;
  }
  A = A.flatMap((n, i, a) => a[i + 1] > n + 1 || a[i + 1] === undefined ? n + 1 : []);
  return A[0];
}

console.log(xInt([-3, 5, 0, 1, -1, 4, 3]));
console.log(xInt([-3, -1]));
console.log(xInt([1, 4, 3, 2]));

相关问题