Encuentre la ocurrencia de números más de N/2 veces en una array ordenada en Java

Dada una array ordenada de n enteros y un entero X, la tarea es encontrar si el entero X aparece más de n/2 veces en la array o no.

Input: arr[] = {1,1,2,3,3,3,3,3,3,3,3,3,4,5,6,6,7}, x=3
Output: 3 occurs 9 times which is more than 8 times

Input: arr[] = {1,1,2,3,3,3,3,3,3,3,3,3,4,5,6,6,7}, x=6
Output: 6 doesn't occur more than 8 times

Enfoque #1:

• Mantenga una variable de conteo, inicialícela con 0.
• Itere sobre la array y compare cada elemento con x, si es igual a x, luego incremente el conteo.
• Después de iterar sobre toda la array, verifique si el valor de la variable de conteo es mayor que n/2 (la mitad de la longitud de la array) o no.
• Si el valor de la variable de conteo es mayor que n/2, imprime «verdadero», de lo contrario, falso.

A continuación se muestra la implementación del enfoque anterior:

// Java Program to check whether element
// x occurs more than n/2 times or not
 
class GFG {
 
    static boolean isOccurMoreThanHalfTimes(int arr[],
                                            int x)
    {
        int len = arr.length;
        // initialize the count by 0
        int count = 0;
        for (int i = 0; i < len; i++) {
            // if x is equal to arr[i],increment the count
            if (arr[i] == x)
                count++;
        }
        // checking the value of count variable
        if (count > len / 2)
            return true;
        else
            return false;
    }
    public static void main(String[] args)
    {
        // driver code
        int arr[] = { 1, 1, 2, 3, 3, 3, 3, 3, 3,
                      3, 3, 3, 4, 5, 6, 6, 7 };
        int x = 3;
        // calling the function and storing
        // the returned result
        boolean answer = isOccurMoreThanHalfTimes(arr, x);
        if (answer) {
            System.out.println("true");
        }
        else {
            System.out.println("false");
        }
    }
}

true

• Complejidad del tiempo- 0(N)
• Complejidad espacial: 0(1)

Enfoque #2:

1. Use una función de límite inferior para encontrar un índice de límite inferior en una array ordenada.
2. Use una función de límite superior para encontrar un índice de límite superior en una array ordenada.
3. Encuentre la diferencia entre el índice de límite superior e inferior.
4. Si la diferencia es mayor que N/2, la impresión ocurre más de N/2.
5. De lo contrario, la impresión no se produce más de N/2 veces.

A continuación se muestra la implementación del enfoque anterior:

class Main {
    public static int lower_bound(int arr[], int low,
                                  int high, int X)
    {
 
        // Base Case
        if (low > high) {
            return low;
        }
 
        // Find the middle index
        int mid = low + (high - low) / 2;
 
        // If arr[mid] is greater than
        // or equal to X then search
        // in left subarray
        if (arr[mid] >= X) {
            return lower_bound(arr, low, mid - 1, X);
        }
 
        // If arr[mid] is less than X
        // then search in right subarray
        return lower_bound(arr, mid + 1, high, X);
    }
 
    // Recursive implementation of
    // upper_bound
    public static int upper_bound(int arr[], int low,
                                  int high, int X)
    {
 
        // Base Case
        if (low > high)
            return low;
 
        // Find the middle index
        int mid = low + (high - low) / 2;
 
        // If arr[mid] is less than
        // or equal to X search in
        // right subarray
        if (arr[mid] <= X) {
            return upper_bound(arr, mid + 1, high, X);
        }
 
        // If arr[mid] is greater than X
        // then search in left subarray
        return upper_bound(arr, low, mid - 1, X);
    }
 
    // Function to implement lower_bound
    // and upper_bound of X
    public static int printBound(int arr[], int N, int X)
    {
        int lower, upper;
        // If lower_bound doesn't exists
        if (arr[0] == X) {
            lower = 0;
        }
        else {
 
            // Find lower_bound
            lower = lower_bound(arr, 0, N, X);
        }
 
        // If upper_bound doesn't exists
        if (arr[N - 1] == X) {
            upper = N - 1;
        }
        else {
 
            // Find upper_bound
            upper = upper_bound(arr, 0, N, X);
        }
        return upper - lower;
    }
 
    public static void main(String[] args)
    {
        int X = 3;
        int arr[] = { 1, 1, 2, 3, 3, 3, 3, 3, 3,
                      3, 3, 3, 4, 5, 6, 6, 7 };
        int occurrence = printBound(arr, arr.length, X);
        if (occurrence >= arr.length / 2) {
            System.out.println(
                X + " occurs " + occurrence
                + " times which is more than "
                + arr.length / 2 + " times");
        }
        else {
            System.out.println(X
                               + " doesn't occur more than "
                               + arr.length / 2 + " times");
        }
    }
}

3 occurs 9 times which is more than 8 times

Complejidad de tiempo: O (log n)