題目的要求是：空間復(fù)雜度為o(1),那么我們就不能考慮用其他的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)
1：時(shí)間復(fù)雜度O(nlogn), 空間復(fù)雜度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;
//中位數(shù)mid, for循環(huán)用來統(tǒng)計(jì)小于等于中位數(shù)的元素個(gè)數(shù)
for (int num: nums) {
if (num <= mid) {
count++;
}
}
//如果個(gè)數(shù)小于等于中位數(shù)說明，這left--mid之間沒有重復(fù)的元素囚玫，繼續(xù)從mid開始遍歷
if (count <= mid) {
left = mid + 1;
} else {//如果個(gè)數(shù)比中位數(shù)大窘问，說明存在重復(fù)的元素臼婆，從left--mid-1繼續(xù)遍歷
right = mid -1;
value = mid;
}
}
return value;
}
2:如果不考慮空間復(fù)雜度那么可以使用hashset或是hashmap來實(shí)現(xiàn)缸沃，利用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:如果不考慮實(shí)現(xiàn)復(fù)雜度的話那么可以考慮雙重循環(huán)遍歷的方式來實(shí)現(xiàn)
時(shí)間復(fù)雜度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;
}
