資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究C++ 中的多數元素 II
假設我們有一個整數陣列；我們必須找到那些出現次數多於 n/3 的下取整的元素。這裡 n 是陣列的大小。
因此，如果輸入類似於 [1,1,1,3,3,2,2,2]，則結果將為 [1,2]
為了解決這個問題，我們將遵循以下步驟：
first := 0, second := 1, cnt1 := 0, cnt2 := 0, n := 陣列 nums 的大小
對於 i 從 0 到 n – 1
x := nums[i]
如果 x 等於 first，則將 cnt1 加 1；
否則，如果 x 等於 second，則將 cnt2 加 1；
否則，如果 cnt1 為 0，則將 first 設定為 x 並將 cnt1 := 1；
否則，如果 cnt2 為 0，則將 second 設定為 x 並將 cnt2 := 1；
否則，將 cnt1 和 cnt2 各減 1。
設定 cnt1 := 0 和 cnt2 := 0
對於 i 從 0 到 n – 1
如果 nums[i] = first，則將 cnt1 加 1，否則如果 nums[i] 等於 second，則將 cnt2 加 1。
建立一個名為 ret 的陣列
如果 cnt1 > n / 3，則將 first 插入 ret 中
如果 cnt2 > n / 3，則將 second 插入 ret 中
返回 ret。
示例 (C++)
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int first = 0;
int second = 1;
int cnt1 = 0;
int cnt2 = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
int x = nums[i];
if(x == first){
cnt1++;
}
else if(x == second){
cnt2++;
}
else if(cnt1 == 0){
first = x;
cnt1 = 1;
}
else if(cnt2 == 0){
second = x;
cnt2 = 1;
} else {
cnt1--;
cnt2--;
}
}
cnt1 = 0;
cnt2 = 0;
for(int i = 0; i < n; i++){
if(nums[i] == first)cnt1++;
else if(nums[i] == second)cnt2++;
}
vector <int> ret;
if(cnt1 > n / 3)ret.push_back(first);
if(cnt2 > n / 3)ret.push_back(second);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1, 1, 1, 3, 3, 2, 2, 2};
print_vector(ob.majorityElement(v));
}輸入
[1,1,1,3,3,2,2,2]
輸出
[2, 1, ]
更新於：2020年5月2日
270 次瀏覽
廣告