logo标签列表

在Java中查找数组中n个缺失元素

javaarraysalgorithmarraylist
13

我有一个数组，其中存储了一些整数。比如说：numbers={3,0,1}或者numbers={9,6,4,2,3,5,7,0,1}。现在我要找出数组中缺失的数字。以这个例子为例，每组中只有一个缺失的数字。第一个数组缺失2，第二个数组缺失8。

我已经编写了代码。我的代码不仅可以从指定的数组中找到一个缺失的数字，还可以找到多个缺失的数字。

但是，如果同一个数组中有连续两个缺失的数字，它就无法找到。

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

但是 ArrayList 支持索引，对吧？ - Kingsley
1
使用列表时，您可以使用get(int)方法而不是下标，将索引作为方法参数。 - Ted Hopp
不过众所周知，Java数组是不可变的 - 不，Java数组是可变的。它们不可调整大小，但它们是可变的。 - user2357112
11个回答
13

这段代码使用了一个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. 输出集合中剩余的项，这些项都是数组中缺失的项。

它如何处理重复的数字？ - Wesam
1
@Wesam HashSet是一种数据结构，当添加重复项时会拒绝它们，因此它仅存储唯一的项。 - forpas
6

将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}。现在如果i的索引是2，则发现numbers [i]和numbers [i-1]之间的差不等于1（4-1 = 3），因此您需要找到介于1和4之间的所有数字，即2、3，因此必须从numbers [i-1]到numbers [i]（不包括）循环以实现此目的。
这段代码的复杂度为大O符号N(O(N))，其中N是数组中最大的元素。
2
public class MissingElement {
    public static void main(String[] args)
    {
        int[] arr={10,9,8,7,5,4,3,1,2};
        Arrays.sort(arr);
        for(int i=0;i<arr.length-1;i++)
        {
            if(arr[i]+1!=arr[i+1])
            {
                System.out.println(arr[i]+1);
                break;
            }
        }
    }
}
2
这里有许多未解答的问题，例如：数组是否总是以零开始？、最大可能的大小是多少？等等。
以下是一种简单的方法来解决这个问题：
  • 找到你的集合中的最大数字。
  • 创建一个空的布尔数组，长度为你在上一步中找到的最大数字加一。
  • 扫描你的原始集合，并将你的新布尔数组中索引等于原始集合中的数字的值设置为true。
  • 最后扫描你的布尔数组，找到并打印所有值为false的索引。
示例：

原始集合：{1,0,3}

  • 步骤1：集合中的最大数字= 3
  • 步骤2：长度为3+1的布尔数组 --> {false, false, false, false}
  • 步骤3：在扫描原始集合并将值设置在布尔数组中时，它将成为最终状态 --> {true, true, false, true}
  • 步骤4：最后扫描布尔数组以打印2，因为它是唯一一个值为false的索引。
我的代码表明，从零开始数组并不是必须的。因为元素取决于数组索引。如果(numbers[0]=0)，那么没问题；如果(numbers[0]=5)，也没问题。重要的是数组是一个排序好的数组。 - Encipher
0
        public static void main(String[] args)
        {
        int[] arr = {1, 2, 3, 5};
        System.out.print("Given number is : ");
        for (int a : arr)
        {
            System.out.print(a + " ");
        }
        int lengthOfArray = arr.length + 1;
        int sum = lengthOfArray * (lengthOfArray + 1) / 2;
        int sumOfArrayNumber = 0;

        for (int s : arr)
        {
            sumOfArrayNumber = sumOfArrayNumber + s;
        }
        System.out.println();
        System.out.println("missing number is : " + Integer.valueOf(sum 
        - sumOfArrayNumber));
        }
0
public static void printMissingNumbers(int[] arr) {
    int length = arr.length;
    int lastIndesx = arr[length - 1];

    while (length != 0) {
        if (arr[length - 1] == lastIndesx) {
            lastIndesx--;
            length--;
        } else {
            System.out.println("missing number :" + lastIndesx);
            lastIndesx--;
        }

    }

}
1
问题中的两个示例输出是什么？ - greybeard
0
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);
    }
}
0
/*// This will work fine for Normal and duplicate elements
1. Find Largest no and create an array of size Largest+1 
2. Add all numbers from the 1 to till largest in set
3. Iterates through the array and remove every item of the array from the set.
4. Prints the remaining items in the set, which are all the missing items of the array.*/

        int numbers[] = { 3, 1, 5, 5 };

        int Largest = numbers[0];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] > Largest) {
                Largest = numbers[i];
            }
        }
        System.out.println("Largest no in given array -->" + Largest);
        
        HashSet<Integer> set = new HashSet<Integer>();

        int arr[] = new int[Largest+1];
        
         for (int i = 1; i < arr.length; i++) {
         set.add(i);
         }

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

        System.out.println("Missing  no are :");
        for (int x : set) {
            System.out.print(x + " ");
        }   
    }
}
请检查您的答案格式。这很令人困惑。 - Bob Claerhout
0
        int[] a= {0,12,14,15,32};
        Arrays.sort(a);
        for(int i=0;i<a.length-1;i++)
        {
            if(a[i+1]-a[i]>1)
            {
                int temp=a[i+1]-a[i];
                for(int j=1;j<temp;j++) 
                {
                 System.out.print(a[i]+j + " ");
                }
                temp=0;
            }
        }

输出：1 2 3 4 5 6 7 8 9 10 11 13 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

0
public class FindingMultipleMissingElements {
public static void main(String args[]) {
    int i = 0;
    int a[] = { 6, 7, 8, 9, 11, 12, 13, 16, 17, 18 };
    int diff = a[0] - 0;
    for (i = 0; i < a.length; i++) {
        if(a[i]-i != diff)
        {
            while(diff<a[i]-i)
            {
                System.out.println(i + diff);
                diff++;
            }
        }
    }

}

}

  • 在这个解决方案中，您可以利用自然数数组中的索引。
  • 初始化diff变量，它存储第一个索引元素6与0（数组中的第一个索引）的差异
  • 为什么要这样做？如果遍历自然数数组并将元素减去所述元素的索引，则应始终返回第一个索引处的值。例如：）6-0=0处的6。7-1=1处的6.8-2=2处的6.9-3=3处的6.11-4=7处的5。请注意此差异。
  • 现在，我们希望遍历整个数组，调用for循环。
  • 我们需要一个条件if语句来检查此差异，并嵌套一个while循环。此while循环将使用索引检查缺失的元素。
  • 一旦计数器达到连续索引，while循环就会终止。
  • 时间复杂度：大O（n）
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接