英文:
Quickest way to find the replaced number
问题
假设我们有一个包含从1到1000000的整数数组。假设一个数字被替换为'-1'。找到被替换的数字的最快方法是什么？除了常规的线性循环/线性搜索之外，是否有更好的方法？
请注意，数组的大小可以是任何值，上面只是一个考虑大型数据的示例。将数组大小表示为“N”，其中包含从1到N的值。
英文:
Let's say we have an Integer array with values from 1 to 1000000. Suppose a single number is replaced with '-1'. What is the quickest way to find the number that is replaced? Is there a better way apart from the normal looping/searching linearly?
Please note the size of the array can be anything, the above is just an example to consider data of large size. Consider the array size as "N" containing the values from 1 to N.
答案1
得分: 1
尝试这样做。
- 将数字填充到一个列表中。
- 将它们随机打乱（以使选择随机）。
- 用-1替换任何索引（返回原始值）
- 现在计算从1到1,000,000（包括1,000,000）的数字的总和。
- 然后遍历列表，从该总和中减去列表中的每个数字。
- 然后通过将
-1的减法纠正为加1到总和中 - 现在总和包含了替换后的数字
int n = 1_000_000;
List<Integer> list = IntStream.rangeClosed(1, n).boxed()
.collect(Collectors.toCollection(ArrayList::new));
Collections.shuffle(list);
int index = 132939; // 选择一个介于1和1,000,000之间的值
int originalValue = list.set(index, -1);
long sum = ((long)n*(n+1))/2L;
for (int i = 0; i < list.size(); i++) {
sum -= list.get(i);
}
System.out.println(sum - 1);
System.out.println(originalValue);
打印结果
351316
351316
英文:
Try it like this.
- populate the numbers in a list.
- shuffle them (to make the choice random).
- replace any index with -1 (returning the original value)
- Now compute the sum of numbers from 1 to 1,000,000 inclusive.
- then iterate thru the list, subtracting each number in the list from that sum.
- then correct the subtraction of
-1by adding1to the sum - sum now contains the replaced number
int n = 1_000_000;
List<Integer> list = IntStream.rangeClosed(1, n).boxed()
.collect(Collectors.toCollection(ArrayList::new));
Collections.shuffle(list);
int index = 132939; // select a value between 1 and 1,000,000 inclusive
int originalValue = list.set(index, -1);
long sum = ((long)n*(n+1))/2L;
for (int i = 0; i < list.size();i++) {
sum -= list.get(i);
}
System.out.println(sum - 1);
System.out.println(originalValue);
prints
351316
351316
</details>
# 答案2
**得分**: 0
我假设数组未排序。
您可以计算等差数列的总和，并在一个循环中从这个总和中减去每个元素。
答案是总和变量的值-1（因为我们在数组中的某个地方减去了-1）。
<details>
<summary>英文:</summary>
I assume that array is not sorted.
You can calculate the sum of an arithmetic sequence and in one loop subtract every element from this sum.
Answer is value of sum variable-1 (because we subtract -1 from array somewhere)
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论