如何在无序的连续整数数组中找到重复的元素?

把所有的数字加起来,然后减去如果只使用1001个数字的话你所期望的总数。

如:

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

Input - Expected => 2

更新2: 有些人认为使用xor来查找重复的数字是一种技巧。对此,我的官方回应是:“我不是在寻找一个重复的数字,我是在寻找一个重复的模式在一系列的位集。而xor绝对比add更适合操作位集”。-)

更新: 为了好玩,在我睡觉之前,这里有一个“单行”的替代解决方案,它不需要额外的存储空间(甚至不需要循环计数器),只接触每个数组元素一次,是非破坏性的,根本不可扩展:-)

printf("Answer : %d\n",
           array[0] ^
           array[1] ^
           array[2] ^
           // continue typing...
           array[999] ^
           array[1000] ^
           1 ^
           2 ^
           // continue typing...
           999^
           1000
      );

注意,编译器实际上会在编译时计算该表达式的后半部分,因此“算法”将在1002个操作中执行。

如果在编译时也知道数组元素的值,编译器会将整个语句优化为一个常量。-)

原始解决方案: 这不符合问题的严格要求,即使它能找到正确的答案。它使用一个额外的整数来保持循环计数器,并且它三次访问每个数组元素-两次在当前迭代中读取和写入它,一次在下一次迭代中读取它。

好吧,在遍历数组时,至少需要一个附加变量(或一个cpu寄存器)来存储当前元素的索引。

除此之外,这里还有一个破坏性的算法,可以安全地扩展到任何n到max_int。

for (int i = 1; i < 1001; i++)
{
   array[i] = array[i] ^ array[i-1] ^ i;
}

printf("Answer : %d\n", array[1000]);

我会给你留下一个简单的提示,让你弄清楚为什么这样做:

a ^ a = 0
0 ^ a = a

弗朗西佩诺夫的非破坏性解决方案。

这可以通过使用 XOR 操作员。

假设我们有一个数组大小 5 : 4, 3, 1, 2, 2
在索引处: 0, 1, 2, 3, 4

现在做一个 异或 所有的元素和指数。我们得到 2 ,这是重复的元素。这是因为, 0 在xoring中不起作用。剩下的 n-1 具有相同的索引对 N-1 数组中的元素和 只有未配对的元素 在数组中是重复的。

int i;
int dupe = 0;
for(i = 0; i < N; i++) {
    dupe = dupe ^ arr[i] ^ i;
}
// dupe has the duplicate.

此解决方案的最佳特性是,它不会遇到基于加法的解决方案中出现的溢出问题。

由于这是一个面试问题,最好从基于加法的解决方案开始,确定溢出限制,然后给出 异或 基于解决方案 :)

这将使用一个附加变量,因此不能完全满足问题中的要求。

把所有的数字加在一起。最后的总和是1+2+…+1000+个重复数。

套用弗朗西斯·佩诺夫的解决方案。

通常的问题是:给定一个任意长度的整数数组,该数组只包含重复次数为偶数的元素,除了重复次数为奇数的一个值外,求出该值。

解决办法是:

acc = 0
for i in array: acc = acc ^ i

你现在的问题是适应。诀窍是你要找到重复两次的元素,所以你需要调整解决方案来弥补这个怪癖。

acc = 0
for i in len(array): acc = acc ^ i ^ array[i]

这就是弗朗西斯的解决方案最终所做的,尽管它破坏了整个数组(顺便说一句,它只能破坏第一个或最后一个元素…)

但是由于索引需要额外的存储空间,我认为如果您也使用一个额外的整数…这种限制很可能是因为他们想阻止您使用数组。

如果他们要求的话,措辞会更准确 O(1) 空间(1000可以看作n,因为这里是任意的)。

加上所有数字。整数1..1000的和是(1000*1001)/2。和你得到的不同是你的号码。

如果你知道我们有精确的数字1-1000,你可以把结果加起来减去 500500 ( sum(1, 1000) )总的来说。这将给出重复的数字,因为 sum(array) = sum(1, 1000) + repeated number .

有一个很简单的方法…1到1000之间的每一个数字只出现一次,除了重复的数字…所以,1…1000的总和是500500。所以,算法是:

sum = 0
for each element of the array:
   sum += that element of the array
number_that_occurred_twice = sum - 500500

python中的单行解决方案

arr = [1,3,2,4,2]
print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0)
# -> 2

解释其工作原理 @Matthieu M.'s answer .

n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s

public static void main(String[] args) {
    int start = 1;
    int end = 10;
    int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10};
    System.out.println(findDuplicate(arr, start, end));
}

static int findDuplicate(int arr[], int start, int end) {

    int sumAll = 0;
    for(int i = start; i <= end; i++) {
        sumAll += i;
    }
    System.out.println(sumAll);
    int sumArrElem = 0;
    for(int e : arr) {
        sumArrElem += e;
    }
    System.out.println(sumArrElem);
    return sumArrElem - sumAll;
}

没有额外的存储需求(除了循环变量)。

int length = (sizeof array) / (sizeof array[0]);
for(int i = 1; i < length; i++) {
   array[0] += array[i];
}

printf(
    "Answer : %d\n",
    ( array[0] - (length * (length + 1)) / 2 )
);

参数和调用堆栈算作辅助存储吗?

int sumRemaining(int* remaining, int count) {
    if (!count) {
        return 0;
    }
    return remaining[0] + sumRemaining(remaining + 1, count - 1);
}

printf("duplicate is %d", sumRemaining(array, 1001) - 500500);

编辑:尾部调用版本

int sumRemaining(int* remaining, int count, int sumSoFar) {
    if (!count) {
        return sumSoFar;
    }
    return sumRemaining(remaining + 1, count - 1, sumSoFar + remaining[0]);
}
printf("duplicate is %d", sumRemaining(array, 1001, 0) - 500500);

public int duplicateNumber(int[] A) {
    int count = 0;
    for(int k = 0; k < A.Length; k++)
        count += A[k];
    return count - (A.Length * (A.Length - 1) >> 1);
}

三角形数t(n)是从1到n的n个自然数之和,可以表示为n(n+1)/2。因此,知道在给定的1001个自然数中,只有一个数是重复的,就可以很容易地求出所有给定数的和并减去t(1000)。结果将包含此副本。

对于一个三角形数t(n),如果n是10的任意幂,也有一种基于基-10表示的求t(n)的漂亮方法:

n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s

我支持将所有元素相加,然后从中减去所有索引的和,但是如果元素的数量很大,这就不起作用。也就是说,它将导致整数溢出!所以我设计了这个算法,它可以在很大程度上减少整数溢出的机会。

   for i=0 to n-1
        begin:  
              diff = a[i]-i;
              dup = dup + diff;
        end
   // where dup is the duplicate element..

但通过这种方法,我将无法找出重复元素所在的索引!

为此,我需要另一次遍历数组,这是不可取的。

基于连续值异或性质对fraci答案的改进:

int result = xor_sum(N);
for (i = 0; i < N+1; i++)
{
   result = result ^ array[i];
}

哪里:

// Compute (((1 xor 2) xor 3) .. xor value)
int xor_sum(int value)
{
    int modulo = x % 4;
    if (modulo == 0)
        return value;
    else if (modulo == 1)
        return 1;
    else if (modulo == 2)
        return i + 1;
    else
        return 0;
}

或者在伪代码/数学语言f(n)中定义为(优化):

if n mod 4 = 0 then X = n
if n mod 4 = 1 then X = 1
if n mod 4 = 2 then X = n+1
if n mod 4 = 3 then X = 0

标准形式f(n)是:

f(0) = 0
f(n) = f(n-1) xor n

我对问题2的回答:

求1-(到)n的和和和和 SUM , PROD .

找出1-n-x-y中数字的和和和积(假设x,y不存在),比如mysum,myprod,

因此:

SUM = mySum + x + y;
PROD = myProd* x*y;

因此:

x*y = PROD/myProd; x+y = SUM - mySum;

如果解这个方程,我们可以找到x,y。

在aux版本中,首先将所有值设置为-1,并在迭代时检查是否已将值插入到aux数组。如果不是(则值必须为-1),则插入。如果你有副本,这是你的解决方案!

在没有aux的情况下,从列表中检索一个元素,并检查列表的其余部分是否包含该值。如果里面有,就在这里找到了。

private static int findDuplicated(int[] array) {
    if (array == null || array.length < 2) {
        System.out.println("invalid");
        return -1;
    }
    int[] checker = new int[array.length];
    Arrays.fill(checker, -1);
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        int checked = checker[value];
        if (checked == -1) {
            checker[value] = value;
        } else {
            return value;
        }
    }
    return -1;
}

private static int findDuplicatedWithoutAux(int[] array) {
    if (array == null || array.length < 2) {
        System.out.println("invalid");
        return -1;
    }
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        for (int j = i + 1; j < array.length; j++) {
            int toCompare = array[j];
            if (value == toCompare) {
                return array[i];
            }
        }
    }
    return -1;
}