องค์ประกอบส่วนใหญ่ II ใน C ++

สมมติว่าเรามีอาร์เรย์จำนวนเต็มหนึ่งอาร์เรย์ เราต้องหาองค์ประกอบเหล่านั้นที่ปรากฎมากกว่าพื้น n/3 โดยที่ n คือขนาดของอาร์เรย์

ดังนั้นหากอินพุตเป็น [1,1,1,3,3,2,2,2] ผลลัพธ์จะเป็น [1,2]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• แรก :=0, วินาที :=1, cnt1 :=0, cnt2 :=0, n :=ขนาดของอาร์เรย์ nums

• สำหรับฉันในช่วง 0 ถึงขนาด n – 1

  • x :=nums[i]

  • ถ้า x เป็นค่าแรก ให้เพิ่ม cnt ขึ้น 1

  • มิฉะนั้นเมื่อ x เป็นวินาที แล้วเพิ่ม cnt2 ขึ้น 1

  • มิฉะนั้นเมื่อ cnt1 เป็น 0 ให้ตั้งค่าเป็น x และ cnt1 ก่อน:=1

  • มิฉะนั้นเมื่อ cnt2 เป็น 0 ให้ตั้งค่าวินาทีเป็น x และ cnt2 :=1

  • มิฉะนั้นจะลดลง cnt1 และ cnt2 โดย 1

• set cnt1 :=0 และ cnt2 :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ถ้า nums[i] =ก่อน ให้เพิ่ม cnt1 ขึ้น 1 มิฉะนั้น เมื่อ nums[i] เป็นอันดับสอง ให้เพิ่ม cnt2 ขึ้น 1

• สร้างอาร์เรย์ที่เรียกว่า ret

• ถ้า cnt1> n / 3 ให้ใส่ ret เข้าไปก่อน

• ถ้า cnt2> n / 3 ให้ใส่วินาทีเข้าไปใน 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, ]