时间戳

首页 > 解决方案 > Codility：缺少整数 - Java SE 8

java - Codility：缺少整数 - Java SE 8

问题描述

即，给定一个由 N 个整数组成的非空零索引数组 A，返回在 A 中不出现的最小正整数（大于 0）。例如，给定：

A[0] = 4   
A[1] = 6   
A[2] = 2   
A[3] = 2   
A[4] = 6   
A[5] = 6
A[6] = 1

该函数应返回 4。假设：

换句话说，对于每个 K (0 <= K <= 50000)，A[K] = 2，给定的实现工作太慢，但函数将返回 50,000

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

N is an integer within the range [1...100,000]
each element of array A is an integer the range [1..N]

我的回答还没有成功！它有什么问题？首先让我说明明显的错误

我的代码有效，但唯一的第一个结果是正确的，第二个不是。

import java.util.*;
class Solution {
        int solution(int[] A) {
        int[] AN = Arrays.stream(A).filter(n -> n > 0).distinct().sorted().toArray();
        int N = AN.length;
        int min = 1;
        int i = 0;
        while (i < N) {
            min = i+1;
            if (min == N) {
                min = Math.max(min , Math.abs(i-N));
            }
            i++;
        }
        return min;
    }
}

标签： java

解决方案

注意：在您给出的示例中，缺少的整数是3而不是4

性能问题可能是由使用distinctand引起的sorted。

我将创建一个基于排序数组的算法，所以它的复杂度是O(n log n).

首先我们对数组进行排序：

Arrays.sort(A);

接下来我们跳过负数或零数

while (i < A.length && A[i] <= 0)
   i++;

如果现在数组已完全解析或当前元素A[i]不是 1，则解为 1。

如果不是这样，我们继续解析数组A，我们将missing变量初始化为 1，如果当前元素等于缺失的元素，我们递增i，或者如果当前元素相等missing + 1，我们递增missing，否则我们停止，我们找到缺失的整数。

最后，如果我们的数组被完全解析并且没有任何不匹配missing variable，A[i]那么我们递增missing.

完整代码：

Arrays.sort(A);

int missing = 1;
int i = 0;
        
while (i < A.length && A[i] <= 0)
   i++;

if (i < A.length && A[i] == 1) {
   while (i < A.length) {
       if (A[i] == missing) {
           i++;
       } else if (A[i] == missing + 1) {
           missing++;
       } else {
           missing++;
           break;
       }
   }
            
   missing = i >= A.length ? missing + 1 : missing;
}

System.out.println(missing);

推荐阅读