题目：

在一个长度为n的数组里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

要求：时间复杂度O(n)，空间复杂度O(1)

分析：如果是只输出重复数字的个数，或者任何一个重复的数字，可以用O(1)的空间复杂度，如果是要输出全部重复的数字，必须要有一个数据载体，那也就是O(n)的空间复杂度，如果用HashMap ，那么空间复杂度也是O(n)，但是借助该数据结构后，算法会更简单，本算法使用《 剑指Offer》（《Codeing Interviews》）中的算法：

Java 版本：

import java.util.ArrayList;
import java.util.List;

public class CI3 {

    public static void main(String args[]) {

        System.out.println("-- begin --");
        List<Integer> result = getDuplicateNumber(new int[]{2, 3, 1, 0, 2, 5, 3});
        if (result != null) {
            result.forEach(System.out::println);
        }
        System.out.println("-- end --");
    }


    private static List<Integer> getDuplicateNumber(int[] inputArray) {
        if (inputArray == null || inputArray.length == 0) {
            return null;
        }
        int length = inputArray.length;
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            while (inputArray[i] != i) {
                if (inputArray[inputArray[i]] == inputArray[i]) {
                    result.add(inputArray[i]);
                    break;
                } else {
                    int temp = inputArray[i];
                    inputArray[i] = inputArray[temp];
                    inputArray[temp] = temp;
                }
            }
        }
        return result;
    }

}

Kotlin版本:

import java.util.ArrayList

fun main(args: Array<String>) {
    println("-- begin --")
    val result = getDuplicateNumber(intArrayOf(2, 3, 1, 0, 2, 5, 3))
    result?.forEach { println(it) }
    println("-- end --")
}

private fun getDuplicateNumber(inputArray: IntArray?): List<Int>? {
    if (inputArray?.isEmpty()!!) {
        return null
    }
    val length = inputArray.size
    val result = ArrayList<Int>()

    for (i in 0 until length) {
        while (inputArray[i] != i) {
            if (inputArray[inputArray[i]] == inputArray[i]) {
                result.add(inputArray[i])
                break
            } else {
                val temp = inputArray[i]
                inputArray[i] = inputArray[temp]
                inputArray[temp] = temp
            }
        }
    }
    return result
}

包含测试的完整代码：https://github.com/chenyucheng97/CodeingInterviews