最近在AP计算机科学A中，我们的班级最近学习了数组。老师向我们提出了一个谜语。 假设你有 20 个数字，包括 10 到 100，对吧？(这些数字是使用扫描仪从另一个文件中收集的)
读取每个数字时，我们必须打印该数字，当且仅当它不是已读取数字的副本时。现在，这里有一个问题。我们必须使用尽可能小的阵列来解决问题。
这就是我遇到的真正问题。我的所有解决方案都需要一个相当大的阵列，其中包含 20 个插槽。
我需要使用数组。我们可以用来有效解决问题的最小阵列是什么？
如果有人可以用伪代码(或文字)解释该方法，那就太棒了。
在最坏的情况下，我们必须使用长度为 19 的数组。 为什么是19？必须记住每个唯一的数字，以便从以下数字中找出重复项。由于您知道有 20 个号码传入，但不会更多，因此您不必存储最后一个号码。要么第 20 个数字已经出现(然后不要执行任何操作)，要么第 20 个数字是唯一的(然后打印并退出 - 无需保存它)。
顺便说一句：我不会称一个长度为 20 大的数组:)
如果您的数字是整数：您的范围从 10 到 100。因此，您需要 91 位来存储已读取的值。Java Long 有 64 位。因此，您将需要一个包含两个长整型的数组。让每个位(多余的位除外)代表 10 到 100 之间的数字。用 0 初始化两个长三角。读取数字时，检查映射到读取值的相应位是否设置为 1。如果是，则读取编号重复，如果不是，则将位设置为 1。
这就是 BitSet 类背后的思想。
同意 Socowi 的观点。如果数是已知的并且它等于N，则总是可以使用N-1数组来存储重复项。一旦收到来自输入的最后一个元素，并且已经知道这是最后一个元素，就不需要将最后一个值存储在重复数组中。
另一个想法。如果你的数字很小，并且确实位于 [10：100] 音调中，您可以使用 1 Long 数来存储至少 2 个小整数，并使用二进制 AND 从长数中提取它们以提取小整数值。在这种情况下，可以使用 N/2 数组。但是这将使在此数组中的搜索更加复杂并且不会节省太多内存，只会减少数组中的项目数。
从技术上讲，您不需要数组，因为输入大小是固定的，因此您只需声明 20 个变量。但是假设它没有修复。
正如其他答案所说，最坏的情况确实是阵列中有 19 个插槽。但是，假设我们在这里谈论的是整数，有一个更好的情况，即一些数字形成一个连续的间隔。在这种情况下，您只需要记住最高和最低数字，因为介于两者之间的任何内容也是重复的。您可以使用间隔数组。
在 10 到 100 的范围内，数字可以间隔开来，在最坏的情况下，您仍然需要一个 19 个间隔的数组。但是，假设最好的情况发生，并且所有数字形成一个连续的间隔，那么您只需要 1 个数组插槽。
您仍然需要解决的问题是在数组上创建一个抽象，当添加元素时，该抽象将自身扩展为 1，因此它将使用所需的最小大小。(类似于ArrayList，但当达到容量时，它的大小会翻倍)。
由于数组在运行时无法更改大小 您需要一个伴随变量来计算不重复的数字，并仅用这些数字部分填充数组。
下面是一个简单的代码，它使用伴随变量currentsize并部分填充数组。
您可以使用在运行时更改大小arrayList的替代方法
final int LENGTH = 20;
double[] numbers = new double[LENGTH];
int currentSize = 0;
Scanner in = new Scanner(System.in);
while (in.hasNextDouble()){
if (currentSize < numbers.length){
numbers[currentSize] = in.nextDouble();
currentSize++;
}
}
编辑
现在，currentSize包含那些不重复的实际数字，并且您没有填充所有20个元素，以防您有一些重复。当然，您需要一些代码来确定数字是否重复。
我的最后一个答案误解了你需要什么，但我打开了这个东西，它使用位移位来做一个 5 个元素的整数数组。由于我们知道最大数字是 100，我们可以在每个索引中存储(相当混乱)四个数字。
Random rand = new Random();
int[] numbers = new int[5];
int curNum;
for (int i = 0; i < 20; i++) {
curNum = rand.nextInt(100);
System.out.println(curNum);
boolean print = true;
for (int x = 0; x < i; x++) {
byte numberToCheck = ((byte) (numbers[(x - (x % 4)) / 4] >>> ((x%4) * 8)));
if (numberToCheck == curNum) {
print = false;
}
}
if (print) {
System.out.println("No Match: " + curNum);
}
int index = ((i - (i % 4)) / 4);
numbers[index] = numbers[index] | (curNum << (((i % 4)) * 8));
}
我使用 rand 来获取我的整数，但您可以轻松地将其更改为扫描仪。