代码之家  ›  专栏  ›  技术社区  ›  myol

数组中未出现的最小正整数

  •  0
  • myol  · 技术社区  · 3 年前

    我正在尝试 this question 使用javascript。当我在网站上运行我的实现时,我得到了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 ,这将返回最大值+1。

    0 回复  |  直到 3 年前
        1
  •  1
  •   Onyambu    3 年前

    不必对数组进行排序,只需查找数组的最大值并在函数中使用它。请注意,您可以使用集合,而不是处理数组。这套 .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]))