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

Question

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

我已经编码了.我的代码不仅从指定的集合中找出一个缺失的数字,它还可以从给定的集合中找出超过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++;
        }
    }
}

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

我想,如果我能够在数字数组中追加2,那么它可能会更容易一些.但是我们都知道Java数组是不可变的,所以我们不能增加它的长度.

所以,也许我会使用List.但是在列表中number[0]=something不支持这种类型的索引.那么我怎么能继续呢.我使用列表还是仍然插入阵列？

所以我尝试用arraylist创建它.

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可以解决我的问题.但是有可能一个简单的数组可以解决这个问题吗？

Answer 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.打印集合中的其余项目,这些项目是阵列中所有缺失的项目.

Answer 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，5，6，7，9}现在，如果i在索引2处，则找到numbers[i]和之间的差numbers[i-1]不等于1（4-1 = 3），现在您需要1和4之间的所有数字都是2、3，因此必须从循环numbers[i-1]到numbers[i]（排他）才能实现此目的。

这段代码的复杂度为O的大O N (O(N))，它N是数组中最大的元素。

Answer 3

int[] numbers = { 11, 6, 4, 5, 7, 1 };
Arrays.sort(numbers);
int numbersArrayIndex = 0;
for (int i = 0; i < numbers[numbers.length - 1]; i++) {
    if (i == numbers[numbersArrayIndex]) {
        numbersArrayIndex++;
    }
    else {
        System.out.println(i);
    }
}