如何找到在洗​​牌连续整数数组重复的元素？ [英] 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屋！