从java中的数组中找出n个缺失的元素

arrays algorithm java arraylist

2022-09-04 08:26:07

我有一个带有一些整数的数组。说，或者说，.现在我必须从数组中找出缺少的数字。根据此示例，每个集合中只有一个缺失的数字。第一个错过2个，第二个错过8个。numbers={3,0,1}numbers={9,6,4,2,3,5,7,0,1}

我已经编写了代码。我的代码不仅可以从指定的集合中找出一个缺失的数字，还可以从给定的集合中找出1个以上的缺失数字。

但是，如果同一集合中缺少两个连续的数字，则无法找出答案。

My code
import java.util.Arrays;

public class Missing_number 
{
    public static void main( String args[] )
    {
        int numbers[]={9,6,4,5,7,0,1};
        Arrays.sort(numbers);
        int i=1;

        while ( i < numbers.length ) 
        {
            if ( numbers[i] - numbers[i-1] == 1 ) 
            {
            } 
            else 
            {
                System.out.println( "Missing number is " + ( numbers[i-1] + 1 ) );
            }
            i++;
        }
    }
}

我正在这样想，如果我能够追加数组中第一个缺失的数字，然后开始搜索，那么代码是什么样子的？现在，这组已经缺少 8 个了。现在，我从列表中终止了另外两个元素（2，3）。输出：根据我的代码：2，8但是3也丢失了，但没有显示。numbers={9,6,4,5,7,0,1}

我在想，如果我能够在数字数组中追加2，那么它可能会容易一点。但众所周知，Java数组是不可变的，因此我们无法增加它的长度。

所以，也许我会使用List。但是在列表中，这种类型的索引不受支持。那么我该如何继续。我是在使用列表还是仍然被困在数组中？number[0]=something

因此，我尝试使用数组列表创建它。

Mycode(modified version from array)

 public class T1 {
 public static void main(String args[]){
    List<Integer> numbers=new ArrayList<>();
    numbers.add(9);
    numbers.add(6);
    numbers.add(4);
    numbers.add(5);
    numbers.add(7);
    numbers.add(0);
    numbers.add(1);
    Collections.sort(numbers);
    int i=1;
    while(i< numbers.size()) {
        if (numbers.get(i) - numbers.get(i-1) == 1) {

        } else {
            System.out.println("Missing number is " + (numbers.get(i-1) + 1));
            numbers.add((numbers.get(i-1)+1));
            Collections.sort(numbers);
        }
        i++;
    }

    }
}

Arraylist可以解决我的问题。但是，一个简单的数组有没有可能解决这个问题呢？

答案 1

此代码使用：HashSet

public static void main(String[] args) {
    int[] numbers = {9, 6, 4, 5, 7, 0, 1};
    Arrays.sort(numbers);
    HashSet<Integer> set = new HashSet<>();

    for (int i = numbers[0]; i < numbers[numbers.length - 1]; i++) {
        set.add(i);
    }

    for (int i = 0; i < numbers.length; i++) {
        set.remove(numbers[i]);
    }

    for (int x : set) {
        System.out.print(x + " ");
    }
}

将打印：

2 3 8

以下是它的工作原理：
1. 将数组的最小数到数组的最大数的所有数字相加到集合中。
2. 循环访问数组并从集合中删除数组的每个项目。
3. 打印集合中剩余的项目，这些项目都是数组中缺少的项目。

答案 2

将子句改为：else

for(int j=numbers[i-1] + 1; j <= numbers[i] - 1; j++) {
    System.out.println( "Missing number is " + ( j ) );
}

让我们检查一下这种情况：{9，6，4，5，7，0，1}排序后它将是：{0，1，4，5，6，7，9}现在如果在索引2处，它发现和之间的差值不等于1（4 - 1 = 3），现在你需要1和4之间的所有数字，它们是2， 3 因此，您必须从循环到（独占）才能实现此目的。inumbers[i]numbers[i-1]numbers[i-1]numbers[i]

此代码的复杂性很大 O of ，其中是数组中最大的元素。N(O(N))N