Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ตรวจสอบองค์ประกอบส่วนใหญ่ในอาร์เรย์ที่จัดเรียงใน C ++


สมมติว่าเรามีอาร์เรย์ เราต้องตรวจสอบว่าจำนวนที่กำหนด x เป็นองค์ประกอบส่วนใหญ่ของอาร์เรย์นั้นหรือไม่ อาร์เรย์ถูกจัดเรียง องค์ประกอบหนึ่งเรียกว่าองค์ประกอบส่วนใหญ่ เมื่อปรากฏ n/2 ครั้งในอาร์เรย์ สมมติว่าอาร์เรย์เป็นเหมือน {1, 2, 3, 3, 3, 3, 6} x =3 ในที่นี้ คำตอบก็เป็นจริงเนื่องจาก 3 เป็นองค์ประกอบส่วนใหญ่ของอาร์เรย์ มี 3s สี่ตัว ขนาดของอาร์เรย์คือ 7 ดังนั้นเราจะเห็น 4> 7/2

เราสามารถนับการเกิดขึ้นของ x ในอาร์เรย์ได้ และหากตัวเลขมากกว่า n/2 คำตอบจะเป็นจริง ไม่เช่นนั้น จะเป็นเท็จ

ตัวอย่าง

#include <iostream>
#include <stack>
using namespace std;
bool isMajorityElement(int arr[], int n, int x){
   int freq = 0;
   for(int i = 0; i<n; i++){
      if(arr[i] == x )
         freq++;
      if(arr[i] > x)
         break;
   }
   return (freq > n/2);
}
int main() {
   int arr[] = {1, 2, 3, 3, 3, 3, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   int x = 3;
   if (isMajorityElement(arr, n, x))
      cout << x << " is the majority element of the array";
   else
      cout << x << " is not the majority element of the array";
}

ผลลัพธ์

3 is the majority element of the array