# （1）找出数组中重复的数字

## 解法1[Java]：动态重排序加判断

public class Solution {
public boolean duplicate(int[] numbers, int length, int[] duplication) {
// check whether the array is valid
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[0] = numbers[i];
return true;
}
swap(numbers, i, numbers[i]);
}
}
return false;
}

private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}


# （2）不修改数组找出重复的数字

## 解法1[C++]：数数判定

#include <iostream>

int countRange(const int* numbers, int length, int start, int end);

// 参数:
//        numbers:     一个整数数组
//        length:      数组的长度
// 返回值:
//        正数  - 输入有效，并且数组中存在重复的数字，返回值为重复的数字
//        负数  - 输入无效，或者数组中没有重复的数字
int getDuplication(const int* numbers, int length)
{
if(numbers == nullptr || length <= 0)
return -1;

int start = 1;
int end = length - 1;
while(end >= start)
{
int middle = ((end - start) >> 1) + start;
int count = countRange(numbers, length, start, middle);
if(end == start)
{
if(count > 1)
return start;
else
break;
}

if(count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return -1;
}

int countRange(const int* numbers, int length, int start, int end)
{
if(numbers == nullptr)
return 0;

int count = 0;
for(int i = 0; i < length; i++)
if(numbers[i] >= start && numbers[i] <= end)
++count;
return count;
}


;