剑指offer面试题[51]-数组中重复的数字

不念不忘少年蓝@ 2022-06-13 12:22 156阅读 0赞

## 题目描述 ##

在一个长度为n的数组里的所有数字都在**0到n-1**的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。

思路：

**       方法一**可以先排序（如快排），然后再依次遍历数组，看前后两个数字是否存在相等的情况。

**方法二**是根据数组中的数字都是在0到n-1之间的范围内。如果这个数字中的没有重复的数字，那么当数组排序之后数字i将出现在下标为i的位置。由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。

现在让我们重排这个数组。从头到尾依次扫描这个数组中的每个数字。当扫面到下标为i的数字时，首先比较这个数字（假设为m）是不是等于i，若等于，接着扫面下一个数字。如果不是，再拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了一个重复的数字（该数字在下标i和小标m的位置都出现了）。如果它和第m个数字不相等，就把**第i个数字和第m个数字进行交换**，把m放到属于它的位置。接下来再重复这个比较、交换的过程，直到我们发现重复的数字。

**注意：写代码之前要注意判断一些边界条件，当然这个题目用哈希表也可以解决。**

参考代码如下：

class Solution {
    public:
        // Parameters:
        //        numbers:     an array of integers
        //        length:      the length of array numbers
        //        duplication: (Output) the duplicated number in the array number
        // Return value:       true if the input is valid, and there are some duplications in the array number
        //                     otherwise false
        //方法1：先排序然后再遍历
        /*
        int partition(int *s, int low, int high)
         {
            int pivot = s[low];
            while (low<high)
            {
                while (low<high&&pivot<=s[high])
                     high--;
                s[low] = s[high];
                while (low<high&&pivot>=s[low])
                     low++;
                s[high] = s[low]; 
            }
            s[low] = pivot;
            return low;
         }
    
        void QSort(int *s, int low, int high)
        {
           if (low<high)   
            {
                int index = partition(s, low, high);
    
                QSort(s, low, index - 1);
                QSort(s, index + 1, high);
            }
        }
    
         void QuikSort(int *s,int length)
         {
            QSort(s, 0, length - 1);
         }
    
         bool duplicate(int numbers[], int length, int* duplication) {
            //尴尬用不了sort，sort(numbers,length);
            //自己写个快排
            QuikSort(numbers,length);
            for (int i = 1; i<length; i++)
            {
              if (numbers[i] == numbers[i - 1])
                {
                    *duplication =numbers[i];
                    return true;
                }
            }
            return false;
         }
        //上述是方法1
        */
        //以下是方法2
        bool duplicate(int numbers[], int length, int* duplication) {
            if(numbers==NULL&&length<=0)
                return false;
            for(int i=0;i<length;i++)
              {
                if(numbers[i]<0||numbers[i]>length-1)
                    return false;
              }
            for(int i=0;i<length;i++)
                {
                  if(numbers[i]!=i)
                      {
                         if(numbers[i]==numbers[numbers[i]])
                             {
                               *duplication=numbers[i];
                               return true;
                             }
                         else
                             swap(numbers[i],numbers[numbers[i]]);
                      }                  
                }
            return false;
        }
        
    };