Phần tử đa số II trong C ++

Giả sử chúng ta có một mảng số nguyên; chúng ta phải tìm những phần tử xuất hiện nhiều hơn tầng của n / 3. Đây là kích thước của mảng.

Vì vậy, nếu đầu vào là [1,1,1,3,3,2,2,2], thì kết quả sẽ là [1,2]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đầu tiên:=0, thứ hai:=1, cnt1:=0, cnt2:=0, n:=kích thước của số mảng

• cho tôi trong phạm vi từ 0 đến kích thước n - 1

  • x:=nums [i]

  • nếu x đứng trước thì tăng cnt lên 1,

  • ngược lại khi x đứng thứ hai thì tăng cnt2 lên 1

  • ngược lại khi cnt1 là 0, thì đặt trước là x và cnt1:=1

  • ngược lại khi cnt2 bằng 0 thì đặt thứ hai là x và cnt2:=1

  • nếu không thì giảm cnt1 và cnt2 đi 1

• đặt cnt1:=0 và cnt2:=0

• cho tôi trong phạm vi từ 0 đến n - 1

  • nếu nums [i] =đầu tiên thì tăng cnt1 lên 1, ngược lại khi nums [i] đứng thứ hai thì tăng cnt2 lên 1

• tạo một mảng được gọi là ret

• nếu cnt1> n / 3, thì hãy chèn trước vào ret

• nếu cnt2> n / 3, thì chèn giây vào ret

• trả lại ret.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[1,1,1,3,3,2,2,2]

Đầu ra

[2, 1, ]