问题: 编写一个C函数，找出给定的整数x在n个整数的排序数组中出现的次数是否超过n/2次。 基本上，我们需要编写一个函数，比如isMajority（），它将数组（arr[]）、数组大小（n）和要搜索的数字（x）作为参数，如果x是一个 多数元素 （超过n/2次）。
null
例如：
Input: arr[] = {1, 2, 3, 3, 3, 3, 10}, x = 3Output: True (x appears more than n/2 times in the given array)Input: arr[] = {1, 1, 2, 4, 4, 4, 6, 6}, x = 4Output: False (x doesn't appear more than n/2 times in the given array)Input: arr[] = {1, 1, 1, 2, 2}, x = 1Output: True (x appears more than n/2 times in the given array)
方法1（使用线性搜索） 线性搜索元素的第一个匹配项，一旦找到它（让它位于索引i），检查索引i+n/2处的元素。如果元素存在于i+n/2，则返回1，否则返回0。
C++
/* C++ Program to check for majority element in a sorted array */ #include<bits/stdc++.h> using namespace std; bool isMajority( int arr[], int n, int x) { int i; /* get last index according to n (even or odd) */ int last_index = n % 2 ? (n / 2 + 1): (n / 2); /* search for first occurrence of x in arr[]*/ for (i = 0; i < last_index; i++) { /* check if x is present and is present more than n/2 times */ if (arr[i] == x && arr[i + n / 2] == x) return 1; } return 0; } /* Driver code */ int main() { int arr[] ={1, 2, 3, 4, 4, 4, 4}; int n = sizeof (arr)/ sizeof (arr[0]); int x = 4; if (isMajority(arr, n, x)) cout << x << " appears more than " << n/2 << " times in arr[]" << endl; else cout <<x << " does not appear more than" << n/2 << " times in arr[]" << endl; return 0; } // This code is contributed by shivanisinghss2110 |
C
/* C Program to check for majority element in a sorted array */ # include <stdio.h> # include <stdbool.h> bool isMajority( int arr[], int n, int x) { int i; /* get last index according to n (even or odd) */ int last_index = n%2? (n/2+1): (n/2); /* search for first occurrence of x in arr[]*/ for (i = 0; i < last_index; i++) { /* check if x is present and is present more than n/2 times */ if (arr[i] == x && arr[i+n/2] == x) return 1; } return 0; } /* Driver program to check above function */ int main() { int arr[] ={1, 2, 3, 4, 4, 4, 4}; int n = sizeof (arr)/ sizeof (arr[0]); int x = 4; if (isMajority(arr, n, x)) printf ( "%d appears more than %d times in arr[]" , x, n/2); else printf ( "%d does not appear more than %d times in arr[]" , x, n/2); return 0; } |
JAVA
/* Program to check for majority element in a sorted array */ import java.io.*; class Majority { static boolean isMajority( int arr[], int n, int x) { int i, last_index = 0 ; /* get last index according to n (even or odd) */ last_index = (n% 2 == 0 )? n/ 2 : n/ 2 + 1 ; /* search for first occurrence of x in arr[]*/ for (i = 0 ; i < last_index; i++) { /* check if x is present and is present more than n/2 times */ if (arr[i] == x && arr[i+n/ 2 ] == x) return true ; } return false ; } /* Driver function to check for above functions*/ public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 4 , 4 , 4 }; int n = arr.length; int x = 4 ; if (isMajority(arr, n, x)== true ) System.out.println(x+ " appears more than " + n/ 2 + " times in arr[]" ); else System.out.println(x+ " does not appear more than " + n/ 2 + " times in arr[]" ); } } /*This article is contributed by Devesh Agrawal*/ |
Python3
'''Python3 Program to check for majority element in a sorted array''' def isMajority(arr, n, x): # get last index according to n (even or odd) */ last_index = (n / / 2 + 1 ) if n % 2 = = 0 else (n / / 2 ) # search for first occurrence of x in arr[]*/ for i in range (last_index): # check if x is present and is present more than n / 2 times */ if arr[i] = = x and arr[i + n / / 2 ] = = x: return 1 # Driver program to check above function */ arr = [ 1 , 2 , 3 , 4 , 4 , 4 , 4 ] n = len (arr) x = 4 if (isMajority(arr, n, x)): print ( "% d appears more than % d times in arr[]" % (x, n / / 2 )) else : print ( "% d does not appear more than % d times in arr[]" % (x, n / / 2 )) # This code is contributed by shreyanshi_arun. |
C#
// C# Program to check for majority // element in a sorted array using System; class GFG { static bool isMajority( int [] arr, int n, int x) { int i, last_index = 0; // Get last index according to // n (even or odd) last_index = (n % 2 == 0) ? n / 2 : n / 2 + 1; // Search for first occurrence // of x in arr[] for (i = 0; i < last_index; i++) { // Check if x is present and // is present more than n/2 times if (arr[i] == x && arr[i + n / 2] == x) return true ; } return false ; } // Driver code public static void Main() { int [] arr = { 1, 2, 3, 4, 4, 4, 4 }; int n = arr.Length; int x = 4; if (isMajority(arr, n, x) == true ) Console.Write(x + " appears more than " + n / 2 + " times in arr[]" ); else Console.Write(x + " does not appear more than " + n / 2 + " times in arr[]" ); } } // This code is contributed by Sam007 |
PHP
<?php // PHP Program to check for // majority element in a // sorted array // function returns majority // element in a sorted array function isMajority( $arr , $n , $x ) { $i ; // get last index according // to n (even or odd) $last_index = $n % 2? ( $n / 2 + 1): ( $n / 2); // search for first occurrence // of x in arr[] for ( $i = 0; $i < $last_index ; $i ++) { // check if x is present and // is present more than n/2 // times if ( $arr [ $i ] == $x && $arr [ $i + $n / 2] == $x ) return 1; } return 0; } // Driver Code $arr = array (1, 2, 3, 4, 4, 4, 4); $n = sizeof( $arr ); $x = 4; if (isMajority( $arr , $n , $x )) echo $x , " appears more than " , floor ( $n / 2), " times in arr[]" ; else echo $x , "does not appear more than " , floor ( $n / 2), "times in arr[]" ; // This code is contributed by Ajit ?> |
Javascript
<script> // Javascript Program to check for majority // element in a sorted array function isMajority(arr, n, x) { let i, last_index = 0; // Get last index according to // n (even or odd) last_index = (n % 2 == 0) ? parseInt(n / 2, 10) : parseInt(n / 2, 10) + 1; // Search for first occurrence // of x in arr[] for (i = 0; i < last_index; i++) { // Check if x is present and // is present more than n/2 times if (arr[i] == x && arr[i + parseInt(n / 2, 10)] == x) return true ; } return false ; } let arr = [ 1, 2, 3, 4, 4, 4, 4 ]; let n = arr.length; let x = 4; if (isMajority(arr, n, x) == true ) document.write(x + " appears more than " + parseInt(n / 2, 10) + " times in arr[]" ); else document.write(x + " does not appear more than " + parseInt(n / 2, 10) + " times in arr[]" ); </script> |
输出：
4 appears more than 3 times in arr[]
时间复杂性： O（n）
辅助空间： O（1）
方法2（使用二进制搜索） 使用二进制搜索方法查找给定数字的第一个匹配项。二进制搜索的标准在这里很重要。
C++
// C++ program to check for majority // element in a sorted array #include<bits/stdc++.h> using namespace std; // If x is present in arr[low...high] // then returns the index of first // occurrence of x, otherwise returns -1 int _binarySearch( int arr[], int low, int high, int x); // This function returns true if the x // is present more than n/2 times in // arr[] of size n bool isMajority( int arr[], int n, int x) { // Find the index of first occurrence // of x in arr[] int i = _binarySearch(arr, 0, n - 1, x); // If element is not present at all, // return false if (i == -1) return false ; // Check if the element is present // more than n/2 times if (((i + n / 2) <= (n - 1)) && arr[i + n / 2] == x) return true ; else return false ; } // If x is present in arr[low...high] then // returns the index of first occurrence // of x, otherwise returns -1 int _binarySearch( int arr[], int low, int high, int x) { if (high >= low) { int mid = (low + high)/2; /*low + (high - low)/2;*/ /* Check if arr[mid] is the first occurrence of x. arr[mid] is first occurrence if x is one of the following is true: (i) mid == 0 and arr[mid] == x (ii) arr[mid-1] < x and arr[mid] == x */ if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x) ) return mid; else if (x > arr[mid]) return _binarySearch(arr, (mid + 1), high, x); else return _binarySearch(arr, low, (mid - 1), x); } return -1; } // Driver code int main() { int arr[] = { 1, 2, 3, 3, 3, 3, 10 }; int n = sizeof (arr) / sizeof (arr[0]); int x = 3; if (isMajority(arr, n, x)) cout << x << " appears more than " << n / 2 << " times in arr[]" << endl; else cout << x << " does not appear more than" << n / 2 << " times in arr[]" << endl; return 0; } // This code is contributed by shivanisinghss2110 |
C
/* C Program to check for majority element in a sorted array */ # include <stdio.h> # include <stdbool.h> /* If x is present in arr[low...high] then returns the index of first occurrence of x, otherwise returns -1 */ int _binarySearch( int arr[], int low, int high, int x); /* This function returns true if the x is present more than n/2 times in arr[] of size n */ bool isMajority( int arr[], int n, int x) { /* Find the index of first occurrence of x in arr[] */ int i = _binarySearch(arr, 0, n-1, x); /* If element is not present at all, return false*/ if (i == -1) return false ; /* check if the element is present more than n/2 times */ if (((i + n/2) <= (n -1)) && arr[i + n/2] == x) return true ; else return false ; } /* If x is present in arr[low...high] then returns the index of first occurrence of x, otherwise returns -1 */ int _binarySearch( int arr[], int low, int high, int x) { if (high >= low) { int mid = (low + high)/2; /*low + (high - low)/2;*/ /* Check if arr[mid] is the first occurrence of x. arr[mid] is first occurrence if x is one of the following is true: (i) mid == 0 and arr[mid] == x (ii) arr[mid-1] < x and arr[mid] == x */ if ( (mid == 0 || x > arr[mid-1]) && (arr[mid] == x) ) return mid; else if (x > arr[mid]) return _binarySearch(arr, (mid + 1), high, x); else return _binarySearch(arr, low, (mid -1), x); } return -1; } /* Driver program to check above functions */ int main() { int arr[] = {1, 2, 3, 3, 3, 3, 10}; int n = sizeof (arr)/ sizeof (arr[0]); int x = 3; if (isMajority(arr, n, x)) printf ( "%d appears more than %d times in arr[]" , x, n/2); else printf ( "%d does not appear more than %d times in arr[]" , x, n/2); return 0; } |
JAVA
/* Java Program to check for majority element in a sorted array */ import java.io.*; class Majority { /* If x is present in arr[low...high] then returns the index of first occurrence of x, otherwise returns -1 */ static int _binarySearch( int arr[], int low, int high, int x) { if (high >= low) { int mid = (low + high)/ 2 ; /*low + (high - low)/2;*/ /* Check if arr[mid] is the first occurrence of x. arr[mid] is first occurrence if x is one of the following is true: (i) mid == 0 and arr[mid] == x (ii) arr[mid-1] < x and arr[mid] == x */ if ( (mid == 0 || x > arr[mid- 1 ]) && (arr[mid] == x) ) return mid; else if (x > arr[mid]) return _binarySearch(arr, (mid + 1 ), high, x); else return _binarySearch(arr, low, (mid - 1 ), x); } return - 1 ; } /* This function returns true if the x is present more than n/2 times in arr[] of size n */ static boolean isMajority( int arr[], int n, int x) { /* Find the index of first occurrence of x in arr[] */ int i = _binarySearch(arr, 0 , n- 1 , x); /* If element is not present at all, return false*/ if (i == - 1 ) return false ; /* check if the element is present more than n/2 times */ if (((i + n/ 2 ) <= (n - 1 )) && arr[i + n/ 2 ] == x) return true ; else return false ; } /*Driver function to check for above functions*/ public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 3 , 3 , 3 , 10 }; int n = arr.length; int x = 3 ; if (isMajority(arr, n, x)== true ) System.out.println(x + " appears more than " + n/ 2 + " times in arr[]" ); else System.out.println(x + " does not appear more than " + n/ 2 + " times in arr[]" ); } } /*This code is contributed by Devesh Agrawal*/ |
Python3
'''Python3 Program to check for majority element in a sorted array''' # This function returns true if the x is present more than n / 2 # times in arr[] of size n */ def isMajority(arr, n, x): # Find the index of first occurrence of x in arr[] */ i = _binarySearch(arr, 0 , n - 1 , x) # If element is not present at all, return false*/ if i = = - 1 : return False # check if the element is present more than n / 2 times */ if ((i + n / / 2 ) < = (n - 1 )) and arr[i + n / / 2 ] = = x: return True else : return False # If x is present in arr[low...high] then returns the index of # first occurrence of x, otherwise returns -1 */ def _binarySearch(arr, low, high, x): if high > = low: mid = (low + high) / / 2 # low + (high - low)//2; ''' Check if arr[mid] is the first occurrence of x. arr[mid] is first occurrence if x is one of the following is true: (i) mid == 0 and arr[mid] == x (ii) arr[mid-1] < x and arr[mid] == x''' if (mid = = 0 or x > arr[mid - 1 ]) and (arr[mid] = = x): return mid elif x > arr[mid]: return _binarySearch(arr, (mid + 1 ), high, x) else : return _binarySearch(arr, low, (mid - 1 ), x) return - 1 # Driver program to check above functions */ arr = [ 1 , 2 , 3 , 3 , 3 , 3 , 10 ] n = len (arr) x = 3 if (isMajority(arr, n, x)): print ( "% d appears more than % d times in arr[]" % (x, n / / 2 )) else : print ( "% d does not appear more than % d times in arr[]" % (x, n / / 2 )) # This code is contributed by shreyanshi_arun. |
C#
// C# Program to check for majority // element in a sorted array */ using System; class GFG { // If x is present in arr[low...high] // then returns the index of first // occurrence of x, otherwise returns -1 static int _binarySearch( int [] arr, int low, int high, int x) { if (high >= low) { int mid = (low + high) / 2; //low + (high - low)/2; // Check if arr[mid] is the first // occurrence of x. arr[mid] is // first occurrence if x is one of // the following is true: // (i) mid == 0 and arr[mid] == x // (ii) arr[mid-1] < x and arr[mid] == x if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x)) return mid; else if (x > arr[mid]) return _binarySearch(arr, (mid + 1), high, x); else return _binarySearch(arr, low, (mid - 1), x); } return -1; } // This function returns true if the x is // present more than n/2 times in arr[] // of size n static bool isMajority( int [] arr, int n, int x) { // Find the index of first occurrence // of x in arr[] int i = _binarySearch(arr, 0, n - 1, x); // If element is not present at all, // return false if (i == -1) return false ; // check if the element is present // more than n/2 times if (((i + n / 2) <= (n - 1)) && arr[i + n / 2] == x) return true ; else return false ; } //Driver code public static void Main() { int [] arr = { 1, 2, 3, 3, 3, 3, 10 }; int n = arr.Length; int x = 3; if (isMajority(arr, n, x) == true ) Console.Write(x + " appears more than " + n / 2 + " times in arr[]" ); else Console.Write(x + " does not appear more than " + n / 2 + " times in arr[]" ); } } // This code is contributed by Sam007 |
Javascript
<script> // Javascript Program to check for majority // element in a sorted array */ // If x is present in arr[low...high] // then returns the index of first // occurrence of x, otherwise returns -1 function _binarySearch(arr, low, high, x) { if (high >= low) { let mid = parseInt((low + high) / 2, 10); //low + (high - low)/2; // Check if arr[mid] is the first // occurrence of x. arr[mid] is // first occurrence if x is one of // the following is true: // (i) mid == 0 and arr[mid] == x // (ii) arr[mid-1] < x and arr[mid] == x if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x)) return mid; else if (x > arr[mid]) return _binarySearch(arr, (mid + 1), high, x); else return _binarySearch(arr, low, (mid - 1), x); } return -1; } // This function returns true if the x is // present more than n/2 times in arr[] // of size n function isMajority(arr, n, x) { // Find the index of first occurrence // of x in arr[] let i = _binarySearch(arr, 0, n - 1, x); // If element is not present at all, // return false if (i == -1) return false ; // check if the element is present // more than n/2 times if (((i + parseInt(n / 2, 10)) <= (n - 1)) && arr[i + parseInt(n / 2, 10)] == x) return true ; else return false ; } let arr = [ 1, 2, 3, 3, 3, 3, 10 ]; let n = arr.length; let x = 3; if (isMajority(arr, n, x) == true ) document.write(x + " appears more than " + parseInt(n / 2, 10) + " times in arr[]" ); else document.write(x + " does not appear more than " + parseInt(n / 2, 10) + " times in arr[]" ); </script> |
输出：
3 appears more than 3 times in arr[]
时间复杂性： O（Logn）
辅助空间： O（1） 算法范例： 分而治之
方法3： 如果已经给出数组已排序且存在多数元素，那么检查特定元素是否与检查数组中间元素是否是我们要检查的数字一样简单。
由于多数元素在数组中出现的次数超过n/2次，因此它始终是中间元素。我们可以使用这个逻辑来检查给定的数字是否是多数元素。
C++
#include <iostream> using namespace std; bool isMajorityElement( int arr[], int n, int key) { if (arr[n / 2] == key) return true ; else return false ; } int main() { int arr[] = { 1, 2, 3, 3, 3, 3, 10 }; int n = sizeof (arr) / sizeof (arr[0]); int x = 3; if (isMajorityElement(arr, n, x)) cout << x << " appears more than " << n / 2 << " times in arr[]" << endl; else cout << x << " does not appear more than" << n / 2 << " times in arr[]" << endl; return 0; } // This code is contributed by shivanisinghss2110 |
C
#include <stdio.h> #include <stdbool.h> bool isMajorityElement( int arr[], int n, int key) { if (arr[n / 2] == key) return true ; else return false ; } int main() { int arr[] = { 1, 2, 3, 3, 3, 3, 10 }; int n = sizeof (arr) / sizeof (arr[0]); int x = 3; if (isMajorityElement(arr, n, x)) printf ( "%d appears more than %d times in arr[]" , x, n / 2); else printf ( "%d does not appear more than %d times in " "arr[]" , x, n / 2); return 0; } |
JAVA
import java.util.*; class GFG{ static boolean isMajorityElement( int arr[], int n, int key) { if (arr[n / 2 ] == key) return true ; else return false ; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 3 , 3 , 3 , 10 }; int n = arr.length; int x = 3 ; if (isMajorityElement(arr, n, x)) System.out.printf( "%d appears more than %d " + "times in arr[]" , x, n / 2 ); else System.out.printf( "%d does not appear more " + "than %d times in " + "arr[]" , x, n / 2 ); } } // This code is contributed by aashish1995 |
Python3
def isMajorityElement(arr, n, key): if (arr[n / / 2 ] = = key): return True return False # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 3 , 3 , 3 , 10 ] n = len (arr) x = 3 if (isMajorityElement(arr, n, x)): print (x, " appears more than " , n / / 2 , " times in arr[]" ) else : print (x, " does not appear more than" , n / / 2 , " times in arr[]" ) # This code is contributed by Chitranayal |
C#
using System; class GFG { static bool isMajorityElement( int []arr, int n, int key) { if (arr[n / 2] == key) return true ; else return false ; } // Driver Code public static void Main(String[] args) { int []arr = { 1, 2, 3, 3, 3, 3, 10 }; int n = arr.Length; int x = 3; if (isMajorityElement(arr, n, x)) Console.Write(x + " appears more than " + n/2 + " times in []arr" ); else Console.Write(x + " does not appear more " + "than " + n/2 + " times in arr[]" ); } } // This code is contributed by aashish1995 |
Javascript
<script> function isMajorityElement(arr, n, key) { if (arr[parseInt(n / 2, 10)] == key) return true ; else return false ; } let arr = [ 1, 2, 3, 3, 3, 3, 10 ]; let n = arr.length; let x = 3; if (isMajorityElement(arr, n, x)) document.write(x + " appears more than " + parseInt(n/2, 10) + " times in arr[]" ); else document.write(x + " does not appear more " + "than " + parseInt(n/2, 10) + " times in arr[]" ); </script> |
输出
3 appears more than 3 times in arr[]
时间复杂性 ：O（1） 辅助空间： O（1）
如果您在上述程序/算法中发现任何错误，或者找到更好的方法来解决相同的问题，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
