剑指Offer——数组中重复的数字
2024-10-12 22:09:14
题目描述:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
分析:
方法1:
用map保存每个数字出现的次数。
方法2:
不需要额外的数组或者hash table来保存,题目里写了数组里数字的范围保证在0 ~ n-1 之间,
所以可以利用现有数组设置标志,当一个数字被访问过后,可以设置对应位上的数+n,
之后再遇到相同的数时,会发现对应位上的数已经大于等于n了,那么直接返回这个数即可。
代码:
方法1:
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
map<int, int> myMap;
for(int i = ; i < length; i++) {
if(myMap[numbers[i]] == ) {
*duplication = numbers[i];
return true;
}
myMap[numbers[i]]++;
}
return false;
}
};
方法2:
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
for(int i = ; i < length; i++) {
int m = numbers[i];
if(m >= length) {
m -= length;
if(numbers[m] == numbers[i]) {
*duplication = m;
return true;
}
}
if(numbers[m] >= length) {
*duplication = m;
return true;
}
numbers[m] += length;
}
return false;
}
};
最新文章
- 疑问,关于win64无法使用debug的问题
- 跨过几个坑,终于完成了我的第一个Xamarin Android App!
- QTableWidget控件总结<;一>;
- Nodejs爬虫进阶=>;异步并发控制
- alarm
- Bean property &#39;**DAO&#39; is not writable or has an invalid setter method
- [原]SQLite的学习系列之获取数据库版本
- 15、SQL基础整理(视图)
- 1709. Penguin-Avia(并查集)
- Oracle DB优化
- 微信公众平台开发(免费云BAE+高效优雅的Python+网站开放的API)
- Leetcode 实施细节 Rotate Image
- AOV网
- Android apk应用程序签名
- 多线程爬坑之路--并发,并行,synchonrized同步的用法
- SourceTree使用方法介绍
- Unable to handle &#39;index&#39; format version &#39;2&#39;, please update rosdistro的解决办法
- 或许,挂掉的点总是出人意料(hw其实蛮有好感的公司)
- 关于iwinfo的调试
- NodeJs——router报错原因