java - 查找不存在的最佳搜索算法

问题描述

在数字范围内查找不存在数字的最佳搜索算法

我在数组上有以下数字范围： [3, -2, -1, 5, 6,7, -9 0, 1,2,3,5,7] 在开始时，我将数组更改为 Set 并使用过滤器只获取正数，我使用 stream().sorted() 按 asc 排序。

在结果列表中，我需要找到第一个不存在的数字。我实现了一个搜索线性算法，我检查下一个值位置减去当前位置值是否小于 2，如果为真，则当前位置值和下一个位置值之间不存在不存在的数字，如果为假，我返回这个数字不存在。

问题是不知道是否有更好的性能方法，但我知道线性算法的搜索成本最高。

我的代码

public static int nopresentnumber(int[] array) {
        if (array == null)
            return 1;
        if (array.length == 0)
            return 1;
        final List<Integer> list = 
                                Arrays.stream(array)
                                    .boxed()
                                    .filter(n -> n > 0)
                                    .sorted()
                                    .collect(Collectors.toSet())
                                    .stream()
                                    .collect(Collectors.toList());
        final int listSize = list.size();
        if (listSize == 0)
            return 1;
        final int min = list.get(0);
        if (min > 1)
            return 1;
        for (int i = 0; i < listSize; i++) {
            if (i < listSize - 1) {
                final int x = list.get(i + 1) - list.get(i);
                if (x > 1)
                    return list.get(i) + 1;
            }
        }
        return list.get(listSize - 1) + 1;
    }

在小范围内使用也不错。例如数组 [3, -2, -1, 5, 6,7, -9, 0, 1,2,3,5,7]，答案是 4。但是如果范围很大并且有这么多的序列号算法太糟糕了。在示例橙色 [-100000... 到 -100000] 上，算法将检查 99999 次。

标签： javaalgorithmliststreamjava-stream

 [3, -2, -1, 5, 6,7, -9, 0, 1, 2, 3, 5, 7]

这个问题的答案似乎是-8考虑到我们正在考虑负数并且我们正在寻找下一个连续缺失的数字。

我下面的解决方案考虑了负数，但如果你只想要正数，添加简单的if检查应该不难。

片段：

import java.util.*;
class MyClass {
    public static void main(String args[]) {
      System.out.println(solve(new int[]{3, -2, -1, 5, 6,7, -9, 0, 1,2,3,5,7}));
    }

    private static int solve(int[] arr){
        Set<Integer> set = new HashSet<>();
        int minimum = arr[0];
        for(int x : arr){
            set.add(x);
            if(minimum > x) minimum = x;
        }

        int find_missing_num = minimum - 1; // just to compare with a base value.

        for(int x : arr){
            if(!set.contains(x-1)){
                if(find_missing_num == minimum - 1 && (x-1) != minimum - 1 || find_missing_num > x - 1) find_missing_num = x - 1;
            }   

            if(!set.contains(x+1)){
                if(find_missing_num == minimum - 1 && (x+1) != minimum - 1 || find_missing_num > x + 1) find_missing_num = x + 1;
            }
        }

        return find_missing_num;
    }
}

演示： https ://ideone.com/KPoiXR

算法：

首先创建一个Set并将所有数组值添加到集合中。
其次是再次遍历数组并检查是否array_element - 1存在array_element + 1。
如果我们没有找到它们，我们会find_missing_num相应地更新我们的代码。
时间复杂度：O(n)，空间复杂度：O(n) 其中n是数组的大小。

要找到第一个缺失的正数（同时忽略数组中的所有负数）：

import java.util.*;
class MyClass {
    public static void main(String args[]) {
      //System.out.println(solve(new int[]{3, -2, -1, 5, 6,7, -9, 0, 1,2,3,5,7}));
      System.out.println(solve(new int[]{-1,0,2,3}));
    }

    private static int solve(int[] arr){
        Set<Integer> set = new HashSet<>();
        int minimum = -1;
        for(int x : arr){
            if(x > -1){
                set.add(x);
                if(minimum > x) minimum = x;
            }
        }

        if(!set.contains(1)) return 1;

        int find_missing_num = - 1; // just to compare with a base value.

        for(int x : arr){
            if(x > -1){
              if(x-1 > 0 && !set.contains(x-1)){
                    if(find_missing_num == -1 || find_missing_num > x - 1) find_missing_num = x - 1;
              }   

              if(!set.contains(x+1)){
                  if(find_missing_num == -1 || find_missing_num > x + 1) find_missing_num = x + 1;
              } 
            }
        }

        return find_missing_num;
    }
}

演示： https ://ideone.com/0gwugF

java - 查找不存在的最佳搜索算法

问题描述

解决方案

推荐阅读