当前位置:网站首页>287. 寻找重复数
287. 寻找重复数
2022-07-06 10:24:00 【ღCauchyོꦿ࿐】
题意
解一
- 二分答案
简单解释,官解也很详细。
定义: d p [ i ] {dp[i]} dp[i] 表示 n u m s [ i ] nums[i] nums[i] 中 < = i <=i <=i 的数的个数。
看这样一个序列:
nums:3 1 3 4 2
dp: 1 2 4 5
性质:自重复的数起,之后所有 d p [ i ] dp[i] dp[i] 都 > i >i >i ,之前都 < = i <=i <=i。
在看这样一个序列:
nums:3 1 3 4 3
dp: 1 1 4 5
尽管重复了多次,但是还是满足上面的性质。
那么我们二分答案,统计 < = m i d <=mid <=mid 的数的个数,如果个数 > m i d >mid >mid ,说明是在右侧,可能是答案, r = m i d r=mid r=mid,否则 l = m i d + 1 l=mid+1 l=mid+1。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
int l = 1, r = n;
while(l < r) {
int mid = (l + r) >> 1;
auto f = [=](int x){
int res = 0;
for (int i = 0; i < n; i++)
if(nums[i] <= x) res += 1;
return res <= x;
};
if(f(mid)) l = mid + 1;
else r = mid;
}
return r;
}
};
/* 一旦加上了重复的数,那么之后一定更大 // 二分check,更小就不要,说明在答案左,l向右调整。 nums: 1 3 2 4 2 [1234]: 1 3 4 5 mid: 3 -> res = 4, r = 3 mid: 2 -> res = 3, r = 2 mid: 1 -> res = 1, l = 2 l == r = 2 nums: 1 3 2 3 4 3 [1234]: 1 2 5 6 mid: 3 -> res = 5, r = 3 mid: 2 -> res = 2, l = 3 l == r = 3 */
解二
二进制
重复一次:
- 重复的数为 x x x, [ 1 , n ] [1,n] [1,n] 都各出现一次,外加 x x x 多出现一次。
- 统计二进制下 1 1 1 的个数,原序列相比 [ 1 , n ] [1,n] [1,n] 序列,多出的 1 1 1 都是由 x x x 产生。
重复多次:
重复的数为 x x x, x x x 代替 [ 1 , n ] [1,n] [1,n] 中没出现的数 y y y,外加 x x x 多出现一次。
四种情况:00、01、10、11(以下x,y表示某一位为1或0)
- x = 0 , y = 0 x=0,y=0 x=0,y=0:<=
- x = 0 , y = 1 x=0,y=1 x=0,y=1:<=
- x = 1 , y = 0 x=1,y=0 x=1,y=0:>
- x = 1 , y = 1 x=1,y=1 x=1,y=1:>
所以,对于 > > > 的情况,将该位 1 1 1 加上即可。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
int res = 0;
for (int i = 0; i < 31; i++) {
int x = 0, y = 0;
for (int j = 0; j < n; j++) {
if(nums[j] & (1 << i)) x += 1;
}
for (int j = 1; j < n; j++) {
if(j & (1 << i)) y += 1;
}
if(x > y) res |= (1 << i);
}
return res;
}
};
解三
- 快慢指针
n + 1 n + 1 n+1个数, [ 1 , n ] [1,n] [1,n] 范围内。每个位置 i i i 连边 i − i- i−> n u m s [ i ] nums[i] nums[i]。
3 1 3 4 2
0 1 2 3 4建边:0->3, 1->1, 2->3, 3->4, 4->2
明显重复的 3 3 3 是环的入口。
又点 0 0 0 只可能有出边,不可能自环。所以定义快慢指针 l , r l,r l,r 都从 0 0 0 开始。
然后就是环形链表找入口的常规解法:
- 慢一步、快二步
- 慢置为 0 0 0
- 慢一步、快一步
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 0, r = 0;
do {
l = nums[l];
r = nums[nums[r]];
} while(l != r);
l = 0;
while(l != r) {
l = nums[l];
r = nums[r];
}
return l;
}
};
边栏推荐
- Codeforces Round #803 (Div. 2)
- 2019 Alibaba cluster dataset Usage Summary
- Kivy tutorial: support Chinese in Kivy to build cross platform applications (tutorial includes source code)
- HMS core machine learning service creates a new "sound" state of simultaneous interpreting translation, and AI makes international exchanges smoother
- The third season of Baidu online AI competition is coming in midsummer, looking for you who love AI!
- 重磅硬核 | 一文聊透对象在 JVM 中的内存布局,以及内存对齐和压缩指针的原理及应用
- Why does wechat use SQLite to save chat records?
- Jerry's access to additional information on the dial [article]
- 解读云原生技术
- Will openeuler last long
猜你喜欢
Alibaba cloud international ECS cannot log in to the pagoda panel console
Heavy! Ant open source trusted privacy computing framework "argot", flexible assembly of mainstream technologies, developer friendly layered design
Grafana 9.0 正式发布!堪称最强!
STM32 key state machine 2 - state simplification and long press function addition
win10系统下插入U盘有声音提示却不显示盘符
Transport layer congestion control - slow start and congestion avoidance, fast retransmission, fast recovery
SAP Fiori 应用索引大全工具和 SAP Fiori Tools 的使用介绍
IP, subnet mask, gateway, default gateway
Is it meaningful for 8-bit MCU to run RTOS?
编译原理——自上而下分析与递归下降分析构造(笔记)
随机推荐
2022 Summer Project Training (I)
std::true_ Type and std:: false_ type
Windows connects redis installed on Linux
STM32按键状态机2——状态简化与增加长按功能
[swoole series 2.1] run the swoole first
Distill knowledge from the interaction model! China University of science and Technology & meituan proposed virt, which combines the efficiency of the two tower model and the performance of the intera
Jerry's watch reading setting status [chapter]
Automatic reservation of air tickets in C language
30 minutes to understand PCA principal component analysis
2022暑期项目实训(二)
High precision operation
UDP protocol: simple because of good nature, it is inevitable to encounter "city can play"
编译原理——预测表C语言实现
Olivetin can safely run shell commands on Web pages (Part 1)
[.Net core] solution to error reporting due to too long request length
Open source and safe "song of ice and fire"
IP, subnet mask, gateway, default gateway
Brief description of SQL optimization problems
C language college laboratory reservation registration system
Excellent open source fonts for programmers