Tenemos una array de solo lectura de n enteros. Encuentre cualquier elemento que aparezca más de n/3 veces en la array en tiempo lineal y espacio adicional constante. Si no existe tal elemento, devuelve -1.
Ejemplos:
Input : [10, 10, 20, 30, 10, 10] Output : 10 10 occurs 4 times which is more than 6/3. Input : [20, 30, 10, 10, 5, 4, 20, 1, 2] Output : -1
La idea se basa en el algoritmo de votación de Moore . Primero encontramos dos candidatos. Luego comprobamos si alguno de estos dos candidatos es realmente mayoría. A continuación se muestra la solución para el enfoque anterior.
C++
// CPP program to find if any element appears
// more than n/3.
#include <bits/stdc++.h>
using namespace std;
int appearsNBy3(int arr[], int n)
{
int count1 = 0, count2 = 0;
int first=INT_MAX , second=INT_MAX ;
for (int i = 0; i < n; i++) {
// if this element is previously seen,
// increment count1.
if (first == arr[i])
count1++;
// if this element is previously seen,
// increment count2.
else if (second == arr[i])
count2++;
else if (count1 == 0) {
count1++;
first = arr[i];
}
else if (count2 == 0) {
count2++;
second = arr[i];
}
// if current element is different from
// both the previously seen variables,
// decrement both the counts.
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// Again traverse the array and find the
// actual counts.
for (int i = 0; i < n; i++) {
if (arr[i] == first)
count1++;
else if (arr[i] == second)
count2++;
}
if (count1 > n / 3)
return first;
if (count2 > n / 3)
return second;
return -1;
}
int main()
{
int arr[] = { 1, 2, 3, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << appearsNBy3(arr, n) << endl;
return 0;
}
Java
// Java program to find if any element appears
// more than n/3.
class GFG {
static int appearsNBy3(int arr[], int n)
{
int count1 = 0, count2 = 0;
// take the integers as the maximum
// value of integer hoping the integer
// would not be present in the array
int first = Integer.MIN_VALUE;;
int second = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// if this element is previously
// seen, increment count1.
if (first == arr[i])
count1++;
// if this element is previously
// seen, increment count2.
else if (second == arr[i])
count2++;
else if (count1 == 0) {
count1++;
first = arr[i];
}
else if (count2 == 0) {
count2++;
second = arr[i];
}
// if current element is different
// from both the previously seen
// variables, decrement both the
// counts.
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// Again traverse the array and
// find the actual counts.
for (int i = 0; i < n; i++) {
if (arr[i] == first)
count1++;
else if (arr[i] == second)
count2++;
}
if (count1 > n / 3)
return first;
if (count2 > n / 3)
return second;
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 1, 1 };
int n = arr.length;
System.out.println(appearsNBy3(arr, n));
}
}
// This code is contributed by Arnab Kundu
Python 3
# Python 3 program to find if # any element appears more than # n/3. import sys def appearsNBy3(arr, n): count1 = 0 count2 = 0 first = sys.maxsize second = sys.maxsize for i in range(0, n): # if this element is # previously seen, # increment count1. if (first == arr[i]): count1 += 1 # if this element is # previously seen, # increment count2. elif (second == arr[i]): count2 += 1 elif (count1 == 0): count1 += 1 first = arr[i] elif (count2 == 0): count2 += 1 second = arr[i] # if current element is # different from both # the previously seen # variables, decrement # both the counts. else: count1 -= 1 count2 -= 1 count1 = 0 count2 = 0 # Again traverse the array # and find the actual counts. for i in range(0, n): if (arr[i] == first): count1 += 1 elif (arr[i] == second): count2 += 1 if (count1 > n / 3): return first if (count2 > n / 3): return second return -1 # Driver code arr = [1, 2, 3, 1, 1 ] n = len(arr) print(appearsNBy3(arr, n)) # This code is contributed by # Smitha
C#
// C# program to find if any element appears
// more than n/3.
using System;
public class GFG {
static int appearsNBy3(int []arr, int n)
{
int count1 = 0, count2 = 0;
// take the integers as the maximum
// value of integer hoping the integer
// would not be present in the array
int first = int.MaxValue;
int second = int.MaxValue;
for (int i = 1; i < n; i++) {
// if this element is previously
// seen, increment count1.
if (first == arr[i])
count1++;
// if this element is previously
// seen, increment count2.
else if (second == arr[i])
count2++;
else if (count1 == 0) {
count1++;
first = arr[i];
}
else if (count2 == 0) {
count2++;
second = arr[i];
}
// if current element is different
// from both the previously seen
// variables, decrement both the
// counts.
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// Again traverse the array and
// find the actual counts.
for (int i = 0; i < n; i++) {
if (arr[i] == first)
count1++;
else if (arr[i] == second)
count2++;
}
if (count1 > n / 3)
return first;
if (count2 > n / 3)
return second;
return -1;
}
// Driver code
static public void Main(String []args)
{
int []arr = { 1, 2, 3, 1, 1 };
int n = arr.Length;
Console.WriteLine(appearsNBy3(arr, n));
}
}
// This code is contributed by Arnab Kundu
PHP
<?php
// PHP program to find if any element appears
// more than n/3.
function appearsNBy3( $arr, $n)
{
$count1 = 0; $count2 = 0;
$first = PHP_INT_MAX ; $second = PHP_INT_MAX ;
for ( $i = 0; $i < $n; $i++) {
// if this element is previously seen,
// increment count1.
if ($first == $arr[$i])
$count1++;
// if this element is previously seen,
// increment count2.
else if ($second == $arr[$i])
$count2++;
else if ($count1 == 0) {
$count1++;
$first = $arr[$i];
}
else if ($count2 == 0) {
$count2++;
$second = $arr[$i];
}
// if current element is different from
// both the previously seen variables,
// decrement both the counts.
else {
$count1--;
$count2--;
}
}
$count1 = 0;
$count2 = 0;
// Again traverse the array and find the
// actual counts.
for ($i = 0; $i < $n; $i++) {
if ($arr[$i] == $first)
$count1++;
else if ($arr[$i] == $second)
$count2++;
}
if ($count1 > $n / 3)
return $first;
if ($count2 > $n / 3)
return $second;
return -1;
}
// Driver code
$arr = array( 1, 2, 3, 1, 1 );
$n = count($arr);
echo appearsNBy3($arr, $n) ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find if any element appears more than n/3.
function appearsNBy3(arr, n)
{
let count1 = 0, count2 = 0;
// take the integers as the maximum
// value of integer hoping the integer
// would not be present in the array
let first = Number.MAX_VALUE;
let second = Number.MAX_VALUE;
for (let i = 1; i < n; i++) {
// if this element is previously
// seen, increment count1.
if (first == arr[i])
count1++;
// if this element is previously
// seen, increment count2.
else if (second == arr[i])
count2++;
else if (count1 == 0) {
count1++;
first = arr[i];
}
else if (count2 == 0) {
count2++;
second = arr[i];
}
// if current element is different
// from both the previously seen
// variables, decrement both the
// counts.
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
// Again traverse the array and
// find the actual counts.
for (let i = 0; i < n; i++) {
if (arr[i] == first)
count1++;
else if (arr[i] == second)
count2++;
}
if (count1 > parseInt(n / 3, 10))
return first;
if (count2 > parseInt(n / 3, 10))
return second;
return -1;
}
let arr = [ 1, 2, 3, 1, 1 ];
let n = arr.length;
document.write(appearsNBy3(arr, n));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
1
Análisis de Complejidad:
- Complejidad de tiempo : O(n)
El primer paso del algoritmo realiza un recorrido completo sobre la array que contribuye a O(n) y se consume otro O(n) para verificar si el recuento 1 y el recuento 2 son mayores que el piso (n/3) veces. - Complejidad del espacio: O(1)
Como no se requiere espacio adicional, la complejidad del espacio es constante
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA