剑指Offer：第三题
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，找出数组中所有重复的数字。
解法一：
先排序在寻找
采用快速排序，时间复杂度是O（nlog（n））

package algorithm.test3;

import java.util.Arrays;
import java.util.HashSet;

public class Q1 {
    public static void main(String[] args) {
        int[] test = new int[]{2, 3, 1, 0, 2, 5, 3};
        quickSort(0,test.length - 1,test);
        HashSet<Integer> integers = new HashSet<>();
        System.out.println(Arrays.toString(test));
        for (int i = 0; i < test.length; i++) {
            if (i == 0) {
                continue;
            }
            if (test[i-1] == test[i]) {
                integers.add( test[i]);
            }
        }
        System.out.println(integers);

    }

    public static void quickSort(int start,int end,int[] test) {
        if (start < end) {
            int partion = getIndex(start, end, test);
            quickSort(start, partion, test);
            quickSort(partion + 1, end, test);
        }
    }

    private static int getIndex(int start, int end, int[] test) {
        // 基准数据
        int tmp = test[start];
        while (start < end) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (start < end && test[end] >= tmp) {
                end--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            test[start] = test[end];
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (start < end && test[start] <= tmp) {
                start++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            test[end] = test[start];

        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
        test[start] = tmp;
        return start; // 返回tmp的正确位置
    }
}

解法二：
原地算法：
时间复杂度O（n）
空间复杂度O（1）

public class Method3 {
    public static void main(String[] args) {

        int[] test = new int[]{2, 3, 1, 0, 2, 5, 3};
        System.out.println(answer2(test));
    }

    public static HashSet<Integer> answer2(int[] test) {
        HashSet<Integer> integers = new HashSet<>();
        for (int i = 0; i < test.length; i++) {
            if (test[i] != i) {
                while (test[i] != i) {
                    if(test[i] == test[test[i]]){
                        integers.add(test[i]);
                        break;
                    }
                    int temp = test[i];
                    test[i] = test[test[i]];
                    test[temp] = temp;
                }
            }

        }
        return integers;
    }
}