Java 找出给定序列中不出现的最小正整数

声明:本页面是StackOverFlow热门问题的中英对照翻译,遵循CC BY-SA 4.0协议,如果您需要使用它,必须同样遵循CC BY-SA许可,注明原文地址和作者信息,同时你必须将它归于原作者(不是我):StackOverFlow 原文地址: http://stackoverflow.com/questions/51719848/
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

提示:将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间:2020-08-11 00:13:26  来源:igfitidea点击:

Find the smallest positive integer that does not occur in a given sequence

javaalgorithm

提问by Chaklader Asfak Arefe

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

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

Write a function:

写一个函数:

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

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

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

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

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

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

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

Assume that:

假使,假设:

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:

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

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

预期的最坏情况时间复杂度为 O(N);预期的最坏情况空间复杂度为 O(N)(不计算输入参数所需的存储空间)。

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);
    }

The score is provided here,

分数在这里提供,

enter image description here

在此处输入图片说明

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

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

采纳答案by Eran

If the expected running time should be linear, you can't use a TreeSet, which sorts the input and therefore requires O(NlogN). Therefore you should use a HashSet, which requires O(N)time to add Nelements.

如果预期的运行时间应该是线性的,则不能使用 a TreeSet,它对输入进行排序,因此需要O(NlogN). 因此您应该使用 a HashSet,这需要O(N)时间来添加N元素。

Besides, you don't need 4 loops. It's sufficient to add all the positive input elements to a HashSet(first loop) and then find the first positive integer not in that Set (second loop).

此外,您不需要 4 个循环。将所有正输入元素添加到HashSet(第一个循环)中,然后找到不在该集合中的第一个正整数(第二个循环)就足够了。

int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        return i;
    }
}

回答by Chaklader Asfak Arefe

I find another solution to do it with additional storage,

我找到了另一种解决方案来增加存储空间,

/*
* if A = [-1,2] the solution works fine
* */
public static int solution(int[] A) {

    int N = A.length;

    int[] C = new int[N];

    /*
     * Mark A[i] as visited by making A[A[i] - 1] negative
     * */
    for (int i = 0; i < N; i++) {

        /*
         * we need the absolute value for the duplicates
         * */
        int j = Math.abs(A[i]) - 1;

        if (j >= 0 && j < N && A[j] > 0) {
            C[j] = -A[j];
        }
    }

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

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

    return N + 1;
}

回答by Anatolii

For the space complexity of O(1)and time complexity of O(N)and if the array can be modified then it could be as follows:

对于 的空间复杂度O(1)和时间复杂度,O(N)如果数组可以修改,则可以如下:

public int getFirstSmallestPositiveNumber(int[] arr) {
    // set positions of non-positive or out of range elements as free (use 0 as marker)
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] <= 0 || arr[i] > arr.length) {
            arr[i] = 0;
        }
    }

    //iterate through the whole array again mapping elements [1,n] to positions [0, n-1]
    for (int i = 0; i < arr.length; i++) {
        int prev = arr[i];
        // while elements are not on their correct positions keep putting them there
        while (prev > 0 && arr[prev - 1] != prev) {
            int next = arr[prev - 1];
            arr[prev - 1] = prev;
            prev = next;
        }
    }

    // now, the first unmapped position is the smallest element
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != i + 1) {
            return i + 1;
        }
    }
    return arr.length + 1;
}

@Test
public void testGetFirstSmallestPositiveNumber() {
    int[][] arrays = new int[][]{{1,-1,-5,-3,3,4,2,8},
      {5, 4, 3, 2, 1}, 
      {0, 3, -2, -1, 1}};

    for (int i = 0; i < arrays.length; i++) {
        System.out.println(getFirstSmallestPositiveNumber(arrays[i]));
    }
}  

Output:

输出:

5

6

2

5

6

2

回答by matt

You're doing too much. You've create a TreeSet which is an order set of integers, then you've tried to turn that back into an array. Instead go through the list, and skip all negative values, then once you find positive values start counting the index. If the index is greater than the number, then the set has skipped a positive value.

你做得太多了。您已经创建了一个 TreeSet,它是一个整数顺序集,然后您尝试将其转换回一个数组。而是遍历列表,跳过所有负值,然后一旦找到正值就开始计算索引。如果索引大于数字,则集合跳过了一个正值。

int index = 1;
for(int a: set){
    if(a>0){
        if(a>index){
            return index;
        } else{
            index++;
        }
    }
}
return index;

Updated for negative values.

更新为负值。

A different solution that is O(n) would be to use an array. This is like the hash solution.

O(n) 的不同解决方案是使用数组。这就像哈希解决方案。

int N = A.length;
int[] hashed = new int[N];

for( int i: A){
    if(i>0 && i<=N){
        hashed[i-1] = 1;
    }
}

for(int i = 0; i<N; i++){
    if(hash[i]==0){
        return i+1;
    }
}
return N+1;

This could be further optimized counting down the upper limit for the second loop.

这可以进一步优化倒计时第二个循环的上限。

回答by Sk Sunny

The code below is is simpler but my motive was to write for JavaScript, ES6 users:

下面的代码更简单,但我的动机是为 JavaScript、ES6 用户编写:

function solution(A) {

    let s = A.sort();
    let max = s[s.length-1];
    let r = 1;

    for(let i=1; i <= (max + 1); i++) {
        r  = A.includes(i) ? 1 : i ;
        if(r>1) break;
    }

    return r;
}

回答by Khawaja Salman Nadeem

I tried it with Swift and got 100%.

我用 Swift 试了一下,结果是 100%。

public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 4.2.1 (Linux)
if A.count == 0 {
    return 1
}
A = A.sorted()
if A[A.count - 1] <= 0 {
    return 1
}

var temp = 1

for numb in A {

    if numb > 0 {

        if numb == temp {
            temp += 1
        }else if numb != (temp - 1) {
            return temp
        }
    }
}

return temp

}

}

回答by ChuckZHB

100% solution in Swift, I found it here, it is really beautiful than mine algo... No need to turn array as ordered, instead using dictionary [Int: Bool]and just check the positive item in dictionary.

Swift 中的 100% 解决方案,我在这里找到了它,它真的比我的算法漂亮……不需要按顺序转换数组,而是使用字典[Int: Bool],只需检查字典中的正项。

public func solution(_ A : inout [Int]) -> Int {
    var counter = [Int: Bool]()
    for i in A {
        counter[i] = true
    }

    var i = 1
    while true {
        if counter[i] == nil {
            return i
        } else {
            i += 1
        }
    }
}

回答by Marcos Curvello

Swift with .reduce()

斯威夫特 .reduce()

public func solution(_ A : inout [Int]) -> Int {
    return A.filter { 
def solution(A):
    max_A=max(A)
    B=set([a if a>=0 else 0 for a in A ])
    b=1
    if max_A<=0:
        return(1)
    else:
        while b in B:
            b+=1
        return(b)
> 0 }.sorted().reduce(1) {
function solution(A) {
    let smallestInt = 1;

    function existsInArray(val) {
        return A.find((a) => a === val);
    }

    for (let index = smallestInt; index < 1000000; index++) {
        if (existsInArray(index) && !existsInArray(index + 1) &&
            existsInArray(smallestInt)) {
            smallestInt = index + 1
        }
    }
    return smallestInt;
}
< ? ##代码## : + 1} }

回答by stratisxen

This answer gives 100% in Python. Worst case complexity O(N).

这个答案在 Python 中给出了 100%。最坏情况复杂度 O(N)。

The idea is that we do not care about negative numbers in the sequence, since we want to find the smallest positive integer not in the sequence A. Hence we can set all negative numbers to zero and keep only the unique positive values. Then we check iteratively starting from 1 whether the number is in the set of positive values of sequence A.

这个想法是我们不关心序列中的负数,因为我们想要找到不在序列 A 中的最小正整数。因此我们可以将所有负数设置为零并只保留唯一的正值。然后我们从 1 开始迭代检查该数字是否在序列 A 的正值集合中。

Worst case scenario, where the sequence is an arithmetic progression with constant difference 1, leads to iterating through all elements and thus O(N) complexity.

最坏的情况是,序列是具有常数差为 1 的等差数列,导致迭代所有元素,因此复杂度为 O(N)。

In the extreme case where all the elements of the sequence are negative (i.e. the maximum is negative) we can immediately return 1 as the minimum positive number.

在序列的所有元素都为负(即最大值为负)的极端情况下,我们可以立即返回 1 作为最小正数。

##代码##

回答by daniel mburu

Solution in JavaScript

JavaScript 中的解决方案

##代码##