Рубрики

Проверьте элемент большинства в отсортированном массиве

Вопрос: Напишите функцию C, чтобы определить, встречается ли данное целое число x более n / 2 раз в отсортированном массиве из n целых чисел.

По сути, нам нужно написать функцию, скажем, isMajority (), которая принимает массив (arr []), размер массива (n) и число для поиска (x) в качестве параметров и возвращает true, если x является элементом большинства (присутствует больше). чем п / 2 раза).

Примеры:

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)

МЕТОД 1 (Использование линейного поиска)
Линейно ищите первое вхождение элемента, как только вы его найдете (пусть по индексу i), проверьте элемент по индексу i + n / 2. Если элемент присутствует в i + n / 2, тогда вернуть 1, иначе вернуть 0.

С

/ * C Программа для проверки большинства элементов в отсортированном массиве * /
# include <stdio.h>
# include <stdbool.h>

  

bool isMajority(int arr[], int n, int x)

{

    int i;

  

    / * получить последний индекс по n (четный или нечетный) * /

    int last_index = n%2? (n/2+1): (n/2);

  

    / * поиск первого вхождения x в arr [] * /

    for (i = 0; i < last_index; i++)

    {

        / * проверить, присутствует ли x и присутствует больше, чем n / 2

           раз * /

        if (arr[i] == x && arr[i+n/2] == x)

            return 1;

    }

    return 0;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

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;

}

Джава

/ * Программа для проверки большинства элементов в отсортированном массиве * /

import java.io.*;

  

class Majority {

  

    static boolean isMajority(int arr[], int n, int x)

    {

        int i, last_index = 0;

  

        / * получить последний индекс по n (четный или нечетный) * /

        last_index = (n%2==0)? n/2: n/2+1;

  

        / * поиск первого вхождения x в arr [] * /

        for (i = 0; i < last_index; i++)

        {

            / * проверить, присутствует ли х и присутствует ли он больше

               чем н / 2 раза * /

            if (arr[i] == x && arr[i+n/2] == x)

                return true;

        }

        return false;

    }

  

    / * Функция драйвера для проверки вышеуказанных функций * /

    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[]");

    }

}
/ * Эта статья предоставлена Девешом Агравалом * /

питон

'' 'Программа Python3 для проверки большинства элементов в отсортированном массиве' ''

  

def isMajority(arr, n, x):

    # получить последний индекс по n (четный или нечетный) * /

    last_index = (n//2 + 1) if n % 2 == 0 else (n//2)

  

    # поиск первого появления x в arr [] * /

    for i in range(last_index):

        # проверить, присутствует ли x и присутствует более n / 2 раза * /

        if arr[i] == x and arr[i + n//2] == x:

            return 1

  
# Программа драйвера для проверки вышеуказанной функции * /

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))

  

  
# Этот код предоставлен shreyanshi_arun.

C #

// C # Программа для проверки большинства
// элемент в отсортированном массиве

using System;

  

class GFG {

    static bool isMajority(int[] arr, 

                            int n, int x)

    {

        int i, last_index = 0;

  

        // Получить последний индекс по

        // n (четное или нечетное)

        last_index = (n % 2 == 0) ? n / 2 :

                                    n / 2 + 1;

  

        // Поиск первого появления

        // из х в обр []

        for (i = 0; i < last_index; i++) {

            // Проверяем, присутствует ли x и

            // присутствует более чем в n / 2 раза

            if (arr[i] == x && arr[i + n / 2] == x)

                return true;

        }

        return false;

    }

  

    // Код драйвера

    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[]");

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// Программа PHP для проверки
// мажоритарный элемент в
// отсортированный массив

  
// функция возвращает большинство
// элемент в отсортированном массиве

function isMajority($arr, $n, $x)

{

    $i;

  

    // получить последний индекс в соответствии

    // в n (четное или нечетное)

    $last_index = $n % 2? ($n / 2 + 1): ($n / 2);

  

    // поиск первого вхождения

    // из х в обр []

    for ($i = 0; $i < $last_index; $i++)

    {

          

        // проверяем наличие х и

        // присутствует больше чем n / 2

        // раз

        if ($arr[$i] == $x && $arr[$i + $n / 2] == $x)

            return 1;

    }

    return 0;

}

  

    // Код драйвера

    $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[]";

                  
// Этот код предоставлен Ajit
?>


Выход :

4 appears more than 3 times in arr[]

Сложность времени: O (n)

МЕТОД 2 (Использование бинарного поиска)
Используйте метод бинарного поиска, чтобы найти первое вхождение данного числа. Критерии бинарного поиска здесь важны.

С

/ * Программа для проверки большинства элементов в отсортированном массиве * /
# include <stdio.h>
# include <stdbool.h>

  
/ * Если x присутствует в arr [low ... high], то возвращает индекс
первое вхождение x, иначе возвращает -1 * /

int _binarySearch(int arr[], int low, int high, int x);

  
/ * Эта функция возвращает true, если x присутствует больше, чем n / 2
раз в обр [] размера п * /

bool isMajority(int arr[], int n, int x)

{

    / * Найти индекс первого появления x в arr [] * /

    int i = _binarySearch(arr, 0, n-1, x);

  

    / * Если элемент вообще отсутствует, вернуть false * /

    if (i == -1)

        return false;

  

    / * проверить, присутствует ли элемент более n / 2 раза * /

    if (((i + n/2) <= (n -1)) && arr[i + n/2] == x)

        return true;

    else

        return false;

}

  
/ * Если x присутствует в arr [low ... high], то возвращает индекс
первое вхождение x, иначе возвращает -1 * /

int _binarySearch(int arr[], int low, int high, int x)

{

    if (high >= low)

    {

        int mid = (low + high)/2; / * низкий + (высокий - низкий) / 2; * /

  

        / * Проверить, является ли arr [mid] первым появлением x.

            arr [mid] является первым появлением, если x является одним из следующих

            правда:

            (i) mid == 0 и arr [mid] == x

            (ii) arr [mid-1] <x и 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;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

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;

}

Джава

/ * Программа для проверки большинства элементов в отсортированном массиве * /

import java.io.*;

  

class Majority {

  

    / * Если x присутствует в arr [low ... high], то возвращает индекс

        первое вхождение x, иначе возвращает -1 * /

    static int  _binarySearch(int arr[], int low, int high, int x)

    {

        if (high >= low)

        {

            int mid = (low + high)/2/ * низкий + (высокий - низкий) / 2; * /

  

            / * Проверить, является ли arr [mid] первым появлением x.

                arr [mid] является первым появлением, если x является одним из следующих

                правда:

                (i) mid == 0 и arr [mid] == x

                (ii) arr [mid-1] <x и 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;

    }

  

  

    / * Эта функция возвращает true, если x присутствует больше, чем n / 2

        раз в обр [] размера п * /

    static boolean isMajority(int arr[], int n, int x)

    {

        / * Найти индекс первого появления x в arr [] * /

        int i = _binarySearch(arr, 0, n-1, x);

  

        / * Если элемент вообще отсутствует, вернуть false * /

        if (i == -1)

            return false;

  

        / * проверить, присутствует ли элемент более n / 2 раза * /

        if (((i + n/2) <= (n -1)) && arr[i + n/2] == x)

            return true;

        else

            return false;

    }

  

    / * Функция драйвера для проверки вышеуказанных функций * /

    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[]");

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

питон

'' 'Программа Python3 для проверки большинства элементов в отсортированном массиве' ''

  
# Эта функция возвращает true, если x присутствует больше, чем n / 2
# раз в arr [] размера n * /

def isMajority(arr, n, x):

      

    # Найти индекс первого появления x в arr [] * /

    i = _binarySearch(arr, 0, n-1, x)

  

    # Если элемент вообще отсутствует, вернуть false * /

    if i == -1:

        return False

  

    # проверить, присутствует ли элемент более n / 2 раза * /

    if ((i + n//2) <= (n -1)) and arr[i + n//2] == x:

        return True

    else:

        return False

  
# Если x присутствует в arr [low ... high], то возвращает индекс
# первое вхождение x, иначе возвращает -1 * /

def _binarySearch(arr, low, high, x):

    if high >= low:

        mid = (low + high)//2 # низкий + (высокий - низкий) // 2;

  

        '' 'Проверьте, является ли arr [mid] первым появлением x.

            arr [mid] является первым появлением, если x является одним из следующих

            правда:

            (i) mid == 0 и arr [mid] == x

            (ii) arr [mid-1] <x и 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

  

  
# Драйверная программа для проверки вышеуказанных функций * /

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))

  
# Этот код предоставлен shreyanshi_arun.

C #

// C # Программа для проверки большинства
// элемент в отсортированном массиве * /

using System;

  

class GFG {

  

    // Если x присутствует в arr [low ... high]

    // затем возвращает индекс первого

    // вхождение x, иначе возвращает -1

    static int _binarySearch(int[] arr, int low,

                               int high, int x)

    {

        if (high >= low) {

            int mid = (low + high) / 2; 

            // низкий + (высокий - низкий) / 2;

  

            // Проверяем, является ли arr [mid] первым

            // вхождение х. обр

            // первое вхождение, если x является одним из

            // верно следующее:

            // (i) mid == 0 и arr [mid] == x

            // (ii) arr [mid-1] <x и 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;

    }

  

    // Эта функция возвращает истину, если х

    // представить больше чем n / 2 раза в arr []

    // размера n

    static bool isMajority(int[] arr, int n, int x)

    {

          

        // Находим индекс первого появления

        // из х в обр []

        int i = _binarySearch(arr, 0, n - 1, x);

  

        // Если элемента нет вообще,

        // вернуть ложь

        if (i == -1)

            return false;

  

        // проверка наличия элемента

        // более чем в n / 2 раза

        if (((i + n / 2) <= (n - 1)) &&

                                arr[i + n / 2] == x)

            return true;

        else

            return false;

    }

  

    // Код драйвера

    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[]");

    }

}

  
// Этот код предоставлен Sam007


Выход:

3 appears more than 3 times in arr[]


Сложность времени:
O (Logn)
Алгоритмическая парадигма: разделяй и властвуй

Пожалуйста, пишите комментарии, если вы найдете какую-либо ошибку в вышеуказанной программе / алгоритме или лучший способ решить ту же проблему.

Рекомендуемые посты:

Проверьте элемент большинства в отсортированном массиве

0.00 (0%) 0 votes