找出给定序列中不出现的最小正整数 [英] Find the smallest positive integer that does not occur in a given sequence

问题描述

我试图解决下面提供的 Codility 中的一个问题，

I was trying to solve a problem in Codility provided below,

写一个函数:

class Solution { public int solution(int[] A); }

即，给定一个由 N 个整数组成的数组 A，返回 A 中不出现的最小正整数(大于 0).

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

例如，给定 A = [1, 3, 6, 4, 1, 2]，函数应该返回 5.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

假设:

N 是 [1..100,000] 范围内的整数；数组 A 的每个元素都是 [−1,000,000..1,000,000] 范围内的整数.复杂性:

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

预期的最坏情况时间复杂度为 O(N)；预期的最坏情况空间复杂度为 O(N)(不包括输入参数所需的存储空间).

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

我在下面编写了性能较低的解决方案，但是，我看不到该错误.

I write the solution below which gives a low performance, however, I can't see the bug.

public static int solution(int[] A) {

        Set<Integer> set = new TreeSet<>();

        for (int a : A) {
            set.add(a);
        }

        int N = set.size();

        int[] C = new int[N];

        int index = 0;

        for (int a : set) {
            C[index++] = a;
        }

        for (int i = 0; i < N; i++) {

            if (C[i] > 0 && C[i] <= N) {
                C[i] = 0;
            }
        }

        for (int i = 0; i < N; i++) {

            if (C[i] != 0) {
                return (i + 1);
            }
        }

        return (N + 1);
    }

分数在此提供，

我会继续调查自己，但如果你能看得更清楚，请告诉我.

I will keep investigating myself, but please inform me if you can see better.

推荐答案

无需存储任何东西.不需要哈希集.(额外的内存)，你可以随心所欲在数组中移动.但是，必须对数组进行排序.我们知道最最小值是 1

No need to store anything. No need for hashsets. (Extra memory), You can do it as you move through the array. However, The array has to be sorted. And we know the very most minimum value is 1

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);     
        int min = 1; 
        /*
         for efficiency — no need to calculate or access the 
         array object’s length property per iteration 
        */
        int cap = A.length; 

        
        for (int i = 0; i < cap; i++){
            if(A[i] == min){
                min++;
            }
        /* 
           can add else if A[i] > min, break; 
           as suggested by punit
         */
        }   
        /*
          min = ( min <= 0 ) ? 1:min; 
          which means: if (min <= 0 ){
          min =1} else {min = min} 
          you can also do: 
          if min <1 for better efficiency/less jumps
         */
        return min;    
    }
}

这篇关于找出给定序列中不出现的最小正整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！