題目： https://leetcode-cn.com/problems/find-majority-element-lcci/
方法一：主要解題思路：先計算陣列每一個元素出現的個數，將這些放進一個新的陣列里面；接著遍歷這個陣列，找出最大值，并且將下標記錄下來（新的陣列和原陣列的下標一一對應），將這個最大值與陣列長度的一般進行比較，如果大于則通過記錄的下標索引陣列元素，就得到目標元素。但這么做會漏掉陣列元素只有一個的情況，因此需要在最開始進行陣列元素個數的判斷。這種解題思路計算量比較大 需要進行優化
代碼如下;
class Solution {
public:
int majorityElement(vector<int>& nums) {
int i = 0;
int result=0;
int hang =(int)nums.size()>>1;
vector<int>sum;
if (nums.size() == 1) return nums[0];
else
{
while (i<nums.size())
{
int num = nums[i];
int len = 0;
for (int j = 0; j < nums.size(); j++) {
if (nums[j] == num) {
len++;
}
}
sum.push_back(len);
i++;
}
int temp = 0;
for (int i = 0; i < sum.size()-1; i++) {
if (temp < sum[i]) {
temp = sum[i];
result = i;
}
}
if(temp>hang) return nums[result];
else return -1;
}
}
};
方法二： 先對一個陣列進行升序排序，這樣元素相等的排在一起，從0號位置
進行遍歷，如果當前位置的元素和它步進陣列長度一半位置的元素相等，則就是我們要找的元素，遍歷到陣列長度的一半結束。
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());//排序
int len = nums.size();
for (int i = 0; i < len < 2; i++){
if (nums[i] == nums[i + len / 2])
return nums[i];
}
return -1;
}
};
方法三：摩爾投票法：演算法解決的問題是如何在任意多的候選人（選票無序），選出獲得票數最多的那個。常見的演算法是掃描一遍選票，對每個候選人進行統計的選票進行統計。當候選人的數目固定時，這個常見演算法的時間復雜度為：O ( n ) O(n)O(n)，當候選人的數目不定時，統計選票可能會執行較長時間，可能需運行o(n^2)的時間 當選票有序時，可以很容易編出數，然后檢查中位數的個數是否超過選票的一半。這篇論文針對無序且侯選人不定的情形，提出了摩爾投票演算法。演算法的比較次數最多是選票（記為n）的兩倍，可以在
O ( n ) O(n)O(n)時間內選出獲票最多的，空間開銷為O ( 1 ) O(1)O(1)。
思路：1、 count = 1； num = nums[0]; 表示從此時開始計算投票。
2.遍歷陣列，如果接下來出現的數字與num相同，count加1。如果不同，count減1。
3如果count=0；則表示目前遍歷到數字可以湊成不同的數對，相互抵消。大于n/2的數字在后面號可以出現，這時從現在這個元素開始計數，令count=1
int check;
int count = 0;
for (int num : nums) {
if (count == 0)
{
check = num;
count = 1;
}
else {
if (num == check) {
count++;
}
else count--;
}
}
count = 0;
for (int num : nums) {
if (num == check) {
count++;
}
}
if (count <= nums.size() / 2) {
return -1;
}
else return check;
uj5u.com熱心網友回復：
采用定樁法就好了，滿足o(n)轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/112020.html
標籤：C++ 語言