找到数组中重复的和丢失的元素

àì夳堔傛蜴生んèń 2022-08-09 12:57 129阅读 0赞

[Find the repeating and the missing number][]

**题目描述**  
Given an unsorted array of size n. Array elements are in range from 1 to n. One number from set \{1, 2, …n\} is missing and one number occurs twice in array. Find these two numbers.

数组无序、范围1~n， 缺一个元素，重复一个元素  
如： arr\[\] = \{3, 1, 3\}  
Output: 2, 3 （缺2， 重复3）

arr\[\] = \{4, 3, 6, 2, 1, 1\}  
Output: 5, 1 （缺5，重复1）

## 方法1 ##

用排序

1) 对数组进行排序
    2) 遍历数组中的元素，找到重复和丢失的数

时间复杂度主要取决于排序算法的选择，空间复杂度为O(1)的情况下可以达到O(nlog(n))

## 方法2 ##

开辟额外的存储空间，相当于hash

1) 建立一个长度为n的空数组temp，初始化为0
    2) 遍历原数组中的元素
        1)if(temp[arr[i]]==0) temp[arr[i]] = 1;
        2)if(temp[arr[i]] == 1) output “arr[i]”（repeating的元素）
    3) 遍历temp数组，输出值为0的元素的index(missing 的元素)

时间复杂度: O(n)  
空间复杂度: O(n)

## 方法3 ##

解方程

1) 遍历数组求数组所有元素的和S与积P
    2) x-y = S - n(n-1)/2
    3) x/y = P/(1*2*...*n)

时间复杂度: O(n)

但是这种方法在计算product的时候容易引起overflow

## 方法4 ##

用数组元素的绝对值做下标，然后让这个下标对应的元素置为负的，相当于把它标记为已访问过的元素，如果某个元素做下标时对应的元素值为负，则这个数是repeating number。再次遍历数组寻找唯一没有置为负的那个元素，它的下标就是缺失的元素值。

#include<stdio.h>
    #include<stdlib.h>
    
    void findElements(int arr[], int size)
    {
        int i;
        printf("\n The repeating element is");
    
        for(i = 0; i < size; i++)
        {
            if(arr[abs(arr[i])-1] > 0)
                arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];
            else
                printf(" %d \n", abs(arr[i]));
        }
    
        printf("the missing element is ");
        for(i=0; i<size; i++)
        {
            if(arr[i]>0)
                printf("%d \n",i+1);
        }
    }

## 方法5 ##

用XOR亦或操作  
任何数与XOR自己都是0

1) res = arr[0]^arr[1]^arr[2].....arr[n-1]
    2) res = res^1^2^3^......^n

最终 res 应该是the missing 和 the repeating number 的亦或，如果取 res 中不为0的一位 bit, 并以此 bit 为标准，将数组中的数分为两个集合：此bit 为1的为一个集合，此bit为0的为一个集合，并将和集合中的数分别取亦或，便可以得到要求的两个数。

3) set_bit = res ^ ~(res-1) //取最右侧的非零位
    4) if(arr[i] & set_bit)
            x = x ^ arr[i]
        else
            y = y ^ arr[i]
    5) if(i & set_bit)
            x = i ^ x
        else
            y = i ^ y

void getTwoElements(int arr[], int n, int *x, int *y)
    {
      int res, set_bit, i;
      *x = 0; *y = 0;
    
      res = arr[0];
      for(i = 1; i < n; i++)
         res = res^arr[i]^i;
       res = res ^ n
    
      /* Get the rightmost set bit in set_bit */
      set_bit = res & ~(res-1);
    
      for(i = 0; i < n; i++)
      {
        if(arr[i] & set_bit)
          *x = *x ^ arr[i]; /* arr[i] belongs to first set */
        else
          *y = *y ^ arr[i]; /* arr[i] belongs to second set*/
        if(i & set_bit)
          *x = *x ^ i; /* i belongs to first set */
        else
          *y = *y ^ i; /* i belongs to second set*/
      }
    
    /* Now *x and *y hold the desired output elements */
    }

[Find the repeating and the missing number]: http://www.geeksforgeeks.org/find-a-repeating-and-a-missing-number/