算法面试：数组编码面试问题
数组数据结构的主要优点是，如果知道索引，它可以提供快速的0（1）搜索，但是从数组中添加和删除元素的速度很慢，因为一旦创建了数组，就无法更改其大小。
要创建更短或更长的数组，您需要创建一个新数组并将所有元素从旧复制到新的。
解决基于数组的问题的关键是熟悉数组数据结构以及基本编程构造函数，如循环，递归和基本运算符。
问题：
在给定的1到100的整数数组中，如何查找缺少的数字？
有关编程访谈的最常见问题之一是，编写一个程序，用Java，C＃或任何其他语言查找数组中缺少的数字。这种编码面试问题不仅在小型初创企业中被问到，而且还在谷歌，亚马逊，Facebook，微软等一些最大的技术公司中提出，主要是当他们访问知名大学的校园招聘毕业生时。这个问题的最简单版本是在100个整数的区域中找到缺失的元素，其中包含1到100之间的数字。这可以通过使用n（n + 1）/ 2计算序列的总和来轻松解决，这是也是最快捷有效的方法之一，但如果数组包含多个缺失的数字或者数组包含重复项，则无法使用它。
这给了面试官一些很好的后续问题，以检查候选人是否可以应用他对略有不同的条件的知识。因此，如果您完成此操作，他们会要求您在重复数组中找到缺少的数字。这可能很棘手但你很快就会发现在数组中找到缺失和重复数字的另一种方法是对它进行排序。
在排序数组中，您可以比较数字是否等于预期的下一个数字。或者，您也可以使用Java中的BitSet来解决此问题。
如何使用Java程序找到缺少的数字
首先理解问题陈述，我们将1到100的数字放入整数数组中，找出丢失的数字的最佳方法是什么？如果访问者特别提到1到100，那么你可以应用上述关于系列总和的技巧，如下所示。如果它有多个缺少的元素，你可以使用BitSet类，当然只有你的面试官允许它。
1）系列之和：公式：n（n + 1）/ 2（但只适用于一个缺失的数字）
2）如果数组有多个缺少的元素，请使用BitSet。
BitSet解决方案，是很好的实用程序类。在许多面试中，当向Java开发人员询问时，他们中的许多人甚至都没有意识到这一点。这个问题是学习如何在Java中使用BitSet的好方法。
如果你要去面试，那么除了这个问题之外，最好还要知道如何在数组和程序中找到重复数字以及找到整数数组中的第二高数字。通常情况下，这些问题会作为后续问题出现。
import java.util.Arrays;
import java.util.BitSet;
/**
* Java program to find missing elements in a Integer array containing
* numbers from 1 to 100.
*
* @author Javin Paul
*/
public class MissingNumberInArray {
public static void main(String args[]) {
// one missing number
printMissingNumber(new int[]{1, 2, 3, 4, 6}, 6);
// two missing number
printMissingNumber(new int[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
// three missing number
printMissingNumber(new int[]{1, 2, 3, 4, 6, 9, 8}, 10);
// four missing number
printMissingNumber(new int[]{1, 2, 3, 4, 9, 8}, 10);
// Only one missing number in array
int[] iArray = new int[]{1, 2, 3, 5};
int missing = getMissingNumber(iArray, 5);
System.out.printf("Missing number in array %s is %d %n",
Arrays.toString(iArray), missing);
}
/**
* A general method to find missing values from an integer array in Java.
* This method will work even if array has more than one missing element.
*/
private static void printMissingNumber(int[] numbers, int count) {
int missingCount = count - numbers.length;
BitSet bitSet = new BitSet(count);
for (int number : numbers) {
bitSet.set(number - 1);
}
System.out.printf("Missing numbers in integer array %s, with total number %d is %n",
Arrays.toString(numbers), count);
int lastMissingIndex = 0;
for (int i = 0; i < missingCount; i++) {
lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
System.out.println(++lastMissingIndex);
}
}
/**
* 在数组中查找缺失数的 java方法
* 仅1到n之间的数字.
* 可用于查找整数数组中缺少的元素
*数字从1到100或1-1000
*/
private static int getMissingNumber(int[] numbers, int totalCount) {
int expectedSum = totalCount * ((totalCount + 1) / 2);
int actualSum = 0;
for (int i : numbers) {
actualSum += i;
}
return expectedSum - actualSum;
}
}
|
输出：
Missing numbers in integer array [1, 2, 3, 4, 6], with total number 6 is 5 Missing numbers in integer array [1, 2, 3, 4, 6, 7, 9, 8, 10], with total number 10 is 5 Missing numbers in integer array [1, 2, 3, 4, 6, 9, 8], with total number 10 is 5 7 10 Missing numbers in integer array [1, 2, 3, 4, 9, 8], with total number 10 is 5 6 7 10 Missing number in array [1, 2, 3, 5] is 4 |
您可以看到，使用正确的数据结构如何轻松解决问题，这是这个程序的关键收获，了解这个技巧是很好的，它只需要计算数字的和，然后从实际的和中减去它，但是如果数组中缺少一个以上的数字，就不能使用这个技巧。另一方面，位集Bitset解决方案更通用，因为您可以使用它在整数数组中查找多个缺少的值。