【剑指Offer】数组中重复的数字

题目描述

• 一个长度是n的数组中的所有数字都在0至n-1范围内。
  数组中存在重复的数字，但不知道有多少个数字是重复的以及每个数字重复多少次。
  请找出数组中任意一个重复的数字。
  例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么输出第一个重复的数字2。
• 考点：数组

解题思路

已知数组中的每一个数字值小于数组长度，如果数组中无任何重复的数字，则数组从小到大排序后理应满足第i个位置对应的元素值是i。利用此特性（数组{2, 3, 1, 0, 2, 5, 3}，指针'|'）：

• |2 3 1 0 2 5 3
  指针'|'此时的位置是0，而数组中位置0的元素值是2，2 != 0，将数组中位置0与位置2的元素相互交换。
• |1 3 2 0 2 5 3
  指针'|'的位置依然是0，而数组中位置0的元素值是1，1 != 0，将数组中位置0与位置1的元素相互交换。
• |3 1 2 0 2 5 3
  指针'|'的位置依然是0，而数组中位置0的元素值是3，3 != 0，将数组中位置0与位置3的元素相互交换。
• |0 1 2 3 2 5 3
  指针'|'的位置依然是0，但数组中位置0的元素值是0，0 == 0，将指针'|'右移一位。
• 0 |1 2 3 2 5 3
  指针'|'此时的位置是1，但数组中位置1的元素值是1，1 == 1，将指针'|'右移一位。
• 0 1 |2 3 2 5 3
  指针'|'此时的位置是2，但数组中位置2的元素值是2，2 == 2，将指针'|'右移一位。
• 0 1 2 |3 2 5 3
  指针'|'此时的位置是3，但数组中位置3的元素值是3，3 == 3，将指针'|'右移一位。
• 0 1 2 3 |2 5 3
  指针'|'此时的位置是4，而数组中位置4的元素值是2，2 != 4，且数组中位置4与位置2的元素值相等，那么输出此元素值。

C++11 (clang++ 3.9)

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
    bool duplicate(int numbers[], int length, int* duplication) {
        if (numbers == 0 || length == 0) {
            return false;  // 数组为空或者数组长度是零，即数组中无任何重复数字
        }
        for (int i = 0; i < length; i++) {  // 指针初始时是位于数组零位置
            while (numbers[i] != i) {  // 当数组中第i位置的元素值不等于i时
                if (numbers[i] == numbers[numbers[i]]) {  // 如果数组中第i位置的元素值A等于数组中第A位置的元素值
                    *duplication = numbers[i];  // 将此元素值A（数组中第一个重复的元素）记录并返回
                    return true;
                }
                else {  // 如果数组中第i位置的元素值A不等于数组中第A位置的元素值，则互相交换这两个位置的元素
                    int temp = numbers[i];  // 将数组中第i位置的元素值暂存至temp中
                    numbers[i] = numbers[temp];  // 将数组中第temp（原第i位置的元素值）位置的元素值赋值于第i位置
                    numbers[temp] = temp;  // 将temp（原第i位置的元素值）赋值于第temp（原第i位置的元素值）位置
                }
            }
        }
        return false;  // 若上述条件均无返回，则直接返回flase（表明数组中并无重复的数字）
    }
};

Java (javac 1.8)

public class Solution {
    public boolean duplicate(int numbers[], int length, int [] duplication) {
        if (numbers == null || length == 0) {
            return false;
        }
        for (int i = 0; i < length; i++) {
            while (numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                else {
                    int temp = numbers[i];
                    numbers[i] = numbers[temp];
                    numbers[temp] = temp;
                }
            }
        }
        return false;
    }
}