題：找出陣列中重復的數字，
題：在一個長度為 n 的陣列 nums 里的所有數字都在 0～n-1 的范圍內，陣列中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次，請找出陣列中任意一個重復的數字，
題中的第一個測驗用例
以及需要引入的頭檔案
可以將下面的方法直接放進去測驗
#include<vector>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
int findRepeatNumber(vector<int> &nums){
size_t slow = 0, fast = 1;
while (fast != nums.size()) {
if (nums[slow++] == nums[fast++])
return nums[slow];
}
return -1;
}
int main(){
vector<int> nums{ 2, 3, 1 , 0 , 2 , 5 , 3 };
findRepeatNumber(nums);
return 0;
}
方法1：
//兩個for回圈，，最后時間超了
//method 1:
int findRepeatNumber(vector<int>& nums) {
for(int i=0;i<nums.size();++i){
for(int j=i+1;j<nums.size();++j){
if(nums[i]==nums[j])
return nums[i];
}
}
return -1;
}
方法2：
//利用sort排序后，利用迭代器，判斷相鄰是否相對
//method 2:
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int>::iterator slow = nums.begin();
vector<int>::iterator fast = slow++;
while (fast != nums.end() ) {
if (*fast == *slow)
cout << *fast;
return *slow;
fast++;
slow++;
}
return -1;
}
方法3：
sort排序后，利用下標，判斷相鄰是否相對
//method 3:
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
size_t slow = 0, fast = 1;
while (fast != nums.size()) {
if (nums[slow++] == nums[fast++])
return nums[slow];
}
return -1;
}
方法4：
//利用無序map，借用多載的[]賦值操作；pair<key,value>
//value的值進行判斷 value 可為bool char等，只要能作為標記即可
//method 4:
int findRepeatNumber(vector<int>& nums) {
std::unordered_map<int,int> u_map;
for(auto e:nums){
if(u_map[e]>0)
return e;
u_map[e]++;
}
return -1;
}
方法5：
//通過判斷 nums[i] i nums[nums[i]] 的關系
//method 5:
int findRepeatNumber(vector<int>& nums) {
int i = 0;
while (i < nums.size()) {
if (nums[i] == i) {
++i;
continue;
}
if (nums[i] == nums[nums[i]])
return nums[i];
swap(nums[i], nums[nums[i]]);
}
return -1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/287241.html
標籤：其他
上一篇：【僵尸大戰植物 Zombies vs.Plants】游戲規則
下一篇：美少女博客轉型