查找所有遗漏的号码

Input:
int array[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };

Output:
Missing number(s): 5, 16, 17, 19, 22.

public class MissingNumber {

    public static int count = 0;
    public static int position = 0;
    public static boolean flag = false;

    public static void main(String[] args) {

        int a[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };

        findMissingNumbers(a, position);

    }

    private static void findMissingNumbers(int a[], int position) {

        if (position == a.length - 1)
            return;

        for (; position < a[a.length - 1]; position++) {

            if ((a[position] - count) != position) {
                System.out.println("Missing Number: " + (position + count));
                flag = true;
                count++;
                break;
            }
        }

        if (flag) {
            flag = false;
            findMissingNumbers(a, position);
        }
    }

}

Missing Number: 5
Missing Number: 16
Missing Number: 17
Missing Number: 19
Missing Number: 22

#1 楼

在三个位置可能缺少数字：



在数组中的第一个数字之前；
在数组中；在数组的最后一个元素之后在
之后。

我会做的是：

static void findMissingNumbers(int[] a, int first, int last) {
            // before the array: numbers between first and a[0]-1
    for (int i = first; i < a[0]; i++) {
        System.out.println(i);
    }
            // inside the array: at index i, a number is missing if it is between a[i-1]+1 and a[i]-1
    for (int i = 1; i < a.length; i++) {
        for (int j = 1+a[i-1]; j < a[i]; j++) {
            System.out.println(j);
        }
    }
            // after the array: numbers between a[a.length-1] and last
    for (int i = 1+a[a.length-1]; i <= last; i++) {
        System.out.println(i);
    }
}

用法示例：

public static void main(String[] args) {
    int a[] = { 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    findMissingNumbers(a, 0, 25);
}

#2 楼

陈述的问题是：


有一个排序的数组。您需要找到所有缺失的数字。编写完整的代码，而不使用任何泛型或内置函数或二进制运算符。将给出第一个和最后一个条件。数组将被排序。数组总是以零开头。


当我在面试中问这样的问题时，我要寻找的一件事是求职者可以阅读规范并为实施做出正确的决定它？规范说明了输入是什么，输出是什么，所以我希望代码中的某处会有一个带有签名的方法

int[] findMissingElements(int[] elements, int first, int last)

请注意，该方法不是void。一种方法将其结果打印出来的想法仅在面试和大学作业中才能找到。

我还希望看到对所提供方法前提条件的一些验证。如果该方法是私有的，则断言是合适的。我还希望看到候选人主动添加一些我没有给出的前提条件。我经常给一些未明确说明的问题，以查看候选人如何处理歧义：通过提出澄清问题，或者通过忽略问题并希望获得最佳解决方案。在这种情况下，并不能说明first小于或等于last，但假设这样做是合理的。

int[] findMissingElements(int[] elements, int first, int last)
{
    assert(elements.Count > 0);
    assert(isSorted(elements));
    assert(elements[0] == 0);
    assert(first <= last); 

如果该方法是公开的，则应if(!precondition) throw ...

#3 楼

关于当前代码：
公共或私有
您有三个public static变量，但您的findMissingNumbers方法是private。最好以其他方式解决。您不希望外部代码修改您的静态变量，这些变量只能由您的findMissingNumbers方法使用。
您提供的findMissingNumbers方法应该是提供一些计算的方法，它应该能够可以从其他类中调用-因此应为public。
命名
boolean flag = false;这是布尔值，当然是标志！标志的作用是什么？现在读取此变量名称根本无法帮助我理解变量的用途。应该说明为什么要使用它。
静态变量

public static int count = 0;
public static int position = 0;
public static boolean flag = false;

具有静态变量通常仅用于常量。这些变量应该是常量吗？常数应标记为final。如果将它们标记为最终，您将很快看到在count和flag上会出现编译器错误，因为您在方法内部修改了这些值。有充分的理由不将它们用作公共静态变量！！
请考虑一下如果您的主要方法如下所示会发生什么：

public static void main(String[] args) {
    int a[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    findMissingNumbers(a, position);

    int b[] = { 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 23 };
    findMissingNumbers(b, position);
}

首次调用findMissingNumbers之后，您的public static变量将已更改，这将修改第二个方法调用的行为。实际上，在这种情况下，它将以很大的方式更改行为，从而导致StackOverflowError。这两个方法调用应该是独立的。
顺便说一句：我认为不需要发送给该方法的position参数，该方法默认应从零开始搜索。
解决方案：
使用更多局部变量。 boolean flag不必是静态变量。它只能在方法本身内使用。它应该是一个局部变量，并初始化为false。进行此更改实际上可以解决两次调用此方法时会出现的问题。
该方法内部使用的变量以及被更改的变量可以作为参数传递给该方法。 StackOverflowError已经是一个参数，因此除了为该方法提供起始值外，实际上未使用公共静态变量。
要为该方法提供默认值，我们可以使用仅调用“实数”的方法“带有一些参数的方法。
这是一个更好的实现，其中修复了代码中的这些缺陷。请注意，position方法之一是findMissingNumbers（因为这是要被调用的方法），而其中一个仍然是public。还要注意改进的变量名称，以及如何在方法之间传递参数-消除了静态变量的巨大缺陷。

public static void main(String[] args) {

    int a[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    findMissingNumbers(a);
    
    int b[] = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    findMissingNumbers(b);

}

private static void findMissingNumbers(int values[], int position, int count) {
    boolean foundMissingNumber = false;
    if (position == values.length - 1)
        return;

    for (; position < values[values.length - 1]; position++) {

        if ((values[position] - count) != position) {
            System.out.println("Missing Number: " + (position + count));
            foundMissingNumber = true;
            count++;
            break;
        }
    }

    if (foundMissingNumber) {
        findMissingNumbers(values, position, count);
    }
}

public static void findMissingNumbers(int values[]) {
    findMissingNumbers(values, 0, 0);
}

另一个有帮助的改进是让您的方法返回缺少的内容数字，而不是在方法内部进行输出。例如，考虑是否要计算丢失数字的总和或丢失数字的平方和。当前，您可能会执行一些代码重复（这是已知的代码味道）来执行此操作，但是如果让您的方法返回丢失的数字，则无需执行任何代码重复。我建议调查一下private以返回值。

#4 楼

关于如何改进算法的几点想法如下：


问题并没有说明总是会有一个遗漏的数字。因此，可能很好（假设第一个值保证为0，因此array[0] == 0），那么如果array[n] != n您有“缺失”值。
如果我们接受这种情况下的缺失值，则n之间的差并且存储在array[n]中的值告诉我们我们有多少“缺失”。

这两点信息将使我们能够将您的算法截断为：


如果没有缺失值，则不执行任何操作。
找到必要的“缺失”数量后，立即停止工作。

#5 楼

除了对静态（全局变量...），正确命名变量（布尔标志）和其他人提到的其他提示的注释之外，我认为还没有提到两件事：代码不符合规范，并且缺少求和公式选项。

您的代码不符合所列规范。

规范要求输出：


缺少编号（s）：5、16、17、19、22。


您的代码显示：

Missing Number: 5 
Missing Number: 16 
Missing Number: 17 
Missing Number: 19 
Missing Number: 22

那不是正确的输出。

您应该将@EricLippers建议的使用

int[] findMissingElements(int[] elements, int first, int last)

的方法与辅助方法配对以打印出结果数组

void printElement(int[] elements)

public static void main(String[] args) {
    int a[] = { 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 23 };
    int b[] = findMissingNumbers(a, 0, 25);
    printArrayToScreen(b[]);
}
int[] findMissingElements(int[] elements, int first, int last) {
    ...
}
void printArrayToScreen(int[] elements){
    ...
}

它分开了职责。这将使将来的更改变得更容易


当您需要更改算法但又不想影响打印时会发生什么？
为未排序的数组添加另一种方法？
添加算法测试？要打印吗？
打印到屏幕上吗？
以HTML格式格式化网站
发送到另一个进程/应用程序

它缺少求和公式选项

/>
如果缺少单个项，我们可以使用求和公式计算所需的总数，并找到实际总数之间的差额。这给出了缺失项。


如果数组缺失一项，则使用求和公式确定缺失项：

a[] = {0,1,3}
4 = `1,3` = 1 + 3
6 = 1 + 2 + 3
2 = 6 - 4
2 is *the* missing number

这可能比遍历未知数目的元素容易。程序员毕竟喜欢选项：)

public static void main(String[] args) {
    int start = 0;
    int end = 5;
    int a[] = {0, 1, 3, 4, 5};
    b[]  = findMissingNumbers(a, start, end);
    printArrayToScreen(b[]);
}
int[] findMissingNumbers(int[] elements, int first, int last) {
    // Length is End+1 with 0 added. Are we only missing one item?
    int numMissing = a.Length - (last + 1);
    if (numMissing = 1) return findMissingNumber(a, start, end);
    // Otherwise, find missing numbers
    ....
}
int[] findMissingNumber(int[] elements, int first, int last) {
    ...
}
void printArrayToScreen(int[] elements){
    ...
}

您想要分离方法，以便可以更改A而不影响B，并且A可以在其他地方重用。

#6 楼

有关样式和封装的其他答案是正确的，但它们缺少重要的优化方法。给定多个缺失值m和总数组长度n，您的解决方案和此页面上的其他解决方案将以O（n）时间返回。实际上，您可以在O（m log n）的时间内完成此操作。

这里的主要见解是，给定排序的输入数组的长度，您可以知道任何给定集合缺少多少个数字端点。如果索引的数量与期望值的数量（即长度为10的数组中期望的10个数字）匹配，则可以放心地假设没有数字丢失。

因此，如果递归将数组二等分，就像在二进位搜寻中一样，那么应该很容易分辨出哪一半都没有遗漏的数字，而只调查不存在的那一半。

0 1 2 4 5 7 8 9 10 11 12 13 14 15  // missing 3 and 6
[-----------] [-----------------]
7 indices,    7 indices,
9 values:     7 values
2 missing     0 missing: do not evaluate!

0 1 2 4 5 7 8
[-----] [---]
4 idxs  3 idxs
5 vals  4 vals
1 msng  1 msng

您的递归函数应大致如下所示：

int[] missingValues(int[] inputArray, int startIndex, int endIndex, int min, int max)

...这留给读者练习。 :)当然，如果缺少很多数字，则此算法可能不会胜过O（n）算法，但如果m比log2(n)小得多，则这是一个更好的算法。

#7 楼

从头开始，可能会重复其他一些答案：



static->我看不出很好的理由
您正在混合计算和输出，对于面试，这是对您的打击

main被调用时带有一系列参数，为了在面试中加分，我会检查参数并使用这些
，您的评论为零，和一些棘手的部分，敲2

flag ..->太通用的名称

position->实际上看起来像是没用的static，您可以只做findMissingNumbers(a, 0);

从面向对象的角度来看，您想重新使用该代码，如果您的一个有趣的方法是private，这将很困难；）
问题指出：将给出第一个和最后一个术语。您没有在代码中使用任何第一项或最后一项，请按3。

我想我可以阅读Java很好。但是我不知道您的代码做什么。当通过调试器运行代码以查看代码的作用比简单地阅读代码要容易时，就会遇到问题。

#8 楼

您可以使用逻辑来比较当前数字和先前数字。如果当前值比前一个值大1，则在长度=差值的当前值上加1。

int prev = a[0];
int current = 0;

for(int i=1;i<a.length;i++)
{
 current = a[i];
 int differenceValue = current-prev;
 if(differenceValue  > 1)
  {
     for(int j=1;j<differenceValue;j++)
     System.out.println("Missing Value : "+(prev+j));
  }
}