// Sort publicstaticintfindDuplicate_sort(int[] nums){ Arrays.sort(nums); int len = nums.length; for (int i = 1; i < len; i++) { if (nums[i] == nums[i - 1]) { return nums[i]; } }
return len; }
复杂度分析
时间复杂度:O(nlogn+n),其中 n 为 nums 数组的长度,O(logn) 排序复杂度,总时间复杂度为 O(nlogn+n)。
// Count publicstaticintfindDuplicate_count(int[] nums){ int len = nums.length; int[] cnt = newint[len + 1]; for (int i = 0; i < len; i++) { cnt[nums[i]]++; if (cnt[nums[i]] > 1) { return nums[i]; } }
return len; }
复杂度分析
时间复杂度:O(n),其中 n 为 nums 数组的长度。
空间复杂度:O(n),需要新建一个长度为 n 的数组。
方法三:HashSet
同方法二,这里使用HashSet来记录数组元素。
1 2 3 4 5 6 7 8 9 10 11 12
// Set publicstaticintfindDuplicate_set(int[] nums){ Set<Integer> set = new HashSet<>(); int len = nums.length; for (int i = 0; i < len; i++) { if (!set.add(nums[i])) { return nums[i]; } }
// Visited publicstaticintfindDuplicate_mark(int[] nums){ int len = nums.length; for (int num : nums) { int idx = Math.abs(num); if (nums[idx] < 0) { return idx; } nums[idx] = -nums[idx]; }
// Binary Search publicstaticintfindDuplicate_bs(int[] nums){ int len = nums.length; int low = 1; int high = len - 1; while (low < high) { int mid = low + (high - low) / 2; int cnt = 0; for (int i = 0; i < len; i++) { if (nums[i] <= mid) { cnt++; } }
if (cnt <= mid) { low = mid + 1; } else { high = mid; } }
// Bit publicstaticintfindDuplicate_bit(int[] nums){ int n = nums.length; int ans = 0; int bit_max = 31; while (((n - 1) >> bit_max) == 0) { bit_max -= 1; }
for (int bit = 0; bit <= bit_max; ++bit) { int x = 0, y = 0; for (int i = 0; i < n; ++i) { if ((nums[i] & (1 << bit)) != 0) { x += 1; } if (i >= 1 && ((i & (1 << bit)) != 0)) { y += 1; } } if (x > y) { ans |= 1 << bit; } }
return ans; }
复杂度分析
时间复杂度:O(nlogn),其中 n 为 nums 数组的长度。O(logn) 代表了我们枚举二进制数的位数个数,枚举第 i 位的时候需要遍历数组统计 x 和 y 的答案,因此总时间复杂度为 O(nlogn)。
// Slow Fast Pointers publicstaticintfindDuplicate_fastSlow(int[] nums){ int slow = 0; int fast = 0; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast);
slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }
return slow; }
复杂度分析
时间复杂度:O(n),其中 n 为 nums 数组的长度。
空间复杂度:O(1)。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)