Pregunta: Escriba una función C para averiguar si un número entero x aparece más de n/2 veces en una array ordenada de n enteros.
Básicamente, necesitamos escribir una función, digamos isMajority(), que tome una array (arr[] ), el tamaño de la array (n) y un número para buscar (x) como parámetros y devuelva verdadero si x es un elemento mayoritario ( presente más de n/2 veces).
Ejemplos:
Input: arr[] = {1, 2, 3, 3, 3, 3, 10}, x = 3
Output: True (x appears more than n/2 times in the given array)
Input: arr[] = {1, 1, 2, 4, 4, 4, 6, 6}, x = 4
Output: False (x doesn't appear more than n/2 times in the given array)
Input: arr[] = {1, 1, 1, 2, 2}, x = 1
Output: True (x appears more than n/2 times in the given array)
MÉTODO 1 (usando la búsqueda lineal): busque linealmente la primera aparición del elemento, una vez que lo encuentre (déjelo en el índice i), verifique el elemento en el índice i + n/2. Si el elemento está presente en i+n/2, devuelve 1; de lo contrario, devuelve 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>
Producción:
4 appears more than 3 times in arr[]
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
MÉTODO 2 (Usando la búsqueda binaria): Use la metodología de búsqueda binaria para encontrar la primera ocurrencia del número dado. El criterio para la búsqueda binaria es importante aquí.
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>
Producción:
3 appears more than 3 times in arr[]
Complejidad de tiempo: O (Iniciar sesión)
Espacio auxiliar: O(1)
Paradigma algorítmico: divide y vencerás
MÉTODO 3: Si ya se ha dado que la array está ordenada y existe un elemento mayoritario, verificar si un elemento en particular es tan fácil como verificar si el elemento central de la array es el número con el que estamos verificando.
Dado que un elemento mayoritario aparece más de n/2 veces en una array, siempre será el elemento central. Podemos usar esta lógica para verificar si el número dado es el elemento mayoritario.
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>
Producción
3 appears more than 3 times in arr[]
Complejidad temporal : O(1)
Espacio auxiliar: O(1)
Escriba comentarios si encuentra algún error en el programa/algoritmo anterior o una mejor manera de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA