287、寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
题解
暴力枚举
class Solution {
public int findDuplicate(int[] nums) {
int res = 0;
for (int i = 0;i < nums.length;i++) {
for (int j = i+1;j < nums.length;j++) {
if (nums[i] == nums[j] ){
res = nums[i];
break;
}
}
if (res != 0) {
break;
}
}
return res;
}
}
二分查找
cnt[i] 表示小于等于i的元素个数, 根据题意，cnt[i]一定是一个随着i单调递增的序列.
二分规则：对于每一个mid,统计小于等于mid的元素数量cnt：
- cnt <= mid : 在有半部分
- cnt > mid : 在左半部分
class Solution {
public int findDuplicate(int[] nums) {
int ans = 0;
int l = 1, r = nums.length - 1;
while (l <= r) {
int mid = (l+r)>>1;
int cnt = 0;
// 统计目标小于等于mid的数量
for (int i = 0;i < nums.length;i++) {
if (nums[i] <= mid) {
cnt++;
}
}
if (cnt <= mid) {
l = mid+1;
} else {
r = mid-1;
ans = mid;
}
}
return ans;
}
}
二进制
统计每一个数字的二进制，第i位的为1的个数。
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length, ans = 0;
int bit_max = 31;
// 求出n-1的二进制有多少位
while (((n - 1) >> bit_max) == 0) {
bit_max -= 1;
}
for(int bit = 0; bit <= bit_max; ++bit) {
// 统计第bit的位的个数
int x = 0,y = 0;
for (int i = 0;i < n;++i) {
// 数组中的信息
if ((nums[i] ^ (1 << bit>>)) ! = 0) {
x += 1;
}
// 1~(n - 1) 的统计
if (i > 1 && ((i & (1 << bit)) != 0) {
y += 1;
}
}
// 还原二进制的每一位
if (x > y) {
ans |= 1 << bit;
}
}
return ans;
}
}
快慢指针
Floyd判圈法。
长度为n的质保函1~n-1的数组，一定存在环！！！！!
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0,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;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
