java--寻找数组中的重复数

题目的要求是：空间复杂度为o(1),那么我们就不能考虑用其他的数据结构来实现
1：时间复杂度O(nlogn), 空间复杂度0(1)

 private static int findDuplicate1(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        int n = nums.length;
        int left = 1;
        int right = n - 1;
        int value = -3;
        while (left <= right) {
            int count = 0;
            int mid = (right - left) / 2 + left;
            //中位数mid, for循环用来统计小于等于中位数的元素个数
            for (int num: nums) {
                if (num <= mid) {
                    count++;
                }
            }
            //如果个数小于等于中位数说明，这left--mid之间没有重复的元素，继续从mid开始遍历
            if (count <= mid) {
                left = mid + 1;
            } else {//如果个数比中位数大，说明存在重复的元素，从left--mid-1继续遍历
                right = mid -1;
                value = mid;
            }
        }
        return value;
    }

2:如果不考虑空间复杂度那么可以使用hashset或是hashmap来实现，利用key的唯一性来保证

public static int findDuplicate(int[] num) {
       if (num == null || num.length <= 0) {
           return 0;
       }
       HashMap<Integer, Integer> hashMap = new HashMap<>();
       for (int i = 0; i < num.length; i++) {
           if (hashMap.containsKey(num[i])) {
               return num[i];
           } else {
               hashMap.put(num[i], i);
           }
       }
       return 0;
   }

3:如果不考虑实现复杂度的话那么可以考虑双重循环遍历的方式来实现
时间复杂度0(n*n)

 private static int findDuplicate2(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }
        return 0;
    }