如何在混洗的连续整数数组中找到重复元素? [英] How to find a duplicate element in an array of shuffled consecutive integers?

问题描述

我最近在某处遇到了一个问题:

I recently came across a question somewhere:

假设您有一个包含 1001 个整数的数组.整数按随机顺序排列，但您知道每个整数都在 1 到 1000(含)之间.此外，每个数字在数组中只出现一次，一个数字除外，它出现了两次.假设您只能访问数组的每个元素一次.描述一个算法来找到重复的数字.如果你在算法中使用了辅助存储，你能找到不需要它的算法吗?

Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

我有兴趣了解的是第二部分，即不使用辅助存储.你有什么想法吗?

What I am interested in to know is the second part, i.e., without using auxiliary storage. Do you have any idea?

推荐答案

只需将它们全部相加，然后从中减去仅使用 1001 个数字时所期望的总数.

Just add them all up, and subtract the total you would expect if only 1001 numbers were used from that.

例如:

Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10

Input - Expected => 2

这篇关于如何在混洗的连续整数数组中找到重复元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！