Q1_1、2、……、n-1、n、n、n+1、……
2022/7/24 6:24:04
本文主要是介绍Q1_1、2、……、n-1、n、n、n+1、……,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Q1_1、2、……、n-1、n、n、n+1、……
图床:blogimg/刷题记录/Q/
刷题代码汇总:https://www.cnblogs.com/geaming/p/16428234.html
题目
存在一个序列1、2、……、n-1、n、n、n+1、……
在这个序列中,只有一个数字有重复,找出重复的数字n
1.若这个序列是有序的,试找到重复数字n
2.若这个序列是无序的,试找到重复数字n
思路
1.例:
下标 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
value | 1 | 2 | 3 | 3 | 4 | 5 |
可以看到如果序列是有序的,重复出现的数字为3
,如果未出现重复数字则value=pos+1
但在出现重复数字之后的序列中value=pos
故可以采用二分法进行查找。先判断arr[mid]==arr[mid+]
,如果相等则返回arr[mid]
,若arr[mid]==mid+1
说明重复数字出现在区间[mid+1,right]
,若arr[mid]==mid
说明重复数字出现在区间[left,mid-1]
,时间复杂度为\(\mathrm{O}(\mathrm{log}n)\)
2.例:
下标 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
value | 5 | 1 | 3 | 4 | 2 | 3 |
这个题如果对于空间复杂度不做要求的话,可以直接使用哈希表进行计算,时间复杂度为\(\mathrm{O}(n)\),而如果我们要求空间复杂度为\(\mathrm{O}(1)\),则不能使用哈希表的做法。
如果将value
视为下一个节点的位置,可以把整个数据看成为一个链表,则问题转换为单链表有环问题。因为有一个value
出现两次,此时形成了环。
代码
1.
#include <iostream> #include <vector> using namespace std; int main() { int a; vector<int> Vec; while (cin >> a) { Vec.push_back(a); if (cin.get() == '\n') break; } //二分查找 int l = 0; int r = Vec.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (Vec[mid] == Vec[mid + 1]) { cout << Vec[mid] << endl; return 0; } else if (Vec[mid] == mid) { r = mid - 1; } else { l = mid + 1; } } }
样例:
输入:1 2 2 3 4
输出:2
输入:1 2 3 3 4
输出:3
2.
#include <iostream> #include <vector> using namespace std; int main() { int a; vector<int> Vec; while (cin >> a) { Vec.push_back(a); if (cin.get() == '\n') break; } //快慢指针 int slow = Vec[0]; int fast = Vec[Vec[0]]; while (slow != fast) { fast = Vec[Vec[fast]]; slow = Vec[slow]; } fast = 0; while (slow != fast) { fast = Vec[fast]; slow = Vec[slow]; } cout << fast << endl; //注意最后返回的是下标值而不是value值 }
补充
单链表有环问题讲解:https://www.bilibili.com/video/BV1kL4y1K7YC
这篇关于Q1_1、2、……、n-1、n、n、n+1、……的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解
- 2024-04-07以一当十丨TiDB 在东吴证券秀财 APP 的应用实践
- 2024-04-07月活超 1.1 亿,用户超 4 亿,你也在用的「知乎」是如何在超大规模 TiDB 集群上玩转多云多活的?来听听知乎代晓磊的答案!