【劍指Offer】【數組】數組中出現次數超過一半的數字
題目：數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出2。如果不存在則輸出0。
A1：用算法類中的sort函數排序，中間的數有可能是出現次數超過數組長度一半的數，保存起來，然后遍歷數組查看該數的個數，若出現次數大于數組長度的一半，則輸出該數 ====> O(nlogn)
A2：用hash存儲數和它出現的次數，若有數出現的次數大于數組長度的一半則輸出 ====> O(n)
//先排序再查找 O(nlogn)
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.empty())
{
return 0;
}
sort(numbers.begin(), numbers.end());
int length_mid = numbers.size() / 2;
int middle = numbers[length_mid];
int count = 0; // 出現次數
for(int i = 0;i < numbers.size(); ++i)
{
if(numbers[i] == middle)
{
++count;
}
}
return (count > length_mid) ? middle : 0;
}
};
//map O(n)
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if (numbers.empty())
{
return 0;
}
int count = 0;
int length_mid = numbers.size() / 2;
map<int, int> m_map;
for(int i = 0; i < numbers.size(); i++)
{
count = ++m_map[numbers[i]];
if(count > length_mid)
{
return numbers[i];
}
}
return 0;
}
};
浙公網安備 33010602011771號