Рубрики

Найти равную (или среднюю) точку в отсортированном массиве с дубликатами

Учитывая отсортированный массив размера n, задача состоит в том, чтобы найти, существует ли элемент в массиве, откуда количество меньших элементов равно количеству больших элементов.

Если Equal Point появляется несколько раз во входном массиве, возвращает индекс его первого появления. Если не существует, вернуть -1.

Примеры :

Input  : arr[] = {1, 2, 3, 3, 3, 3}
Output : 1
Equal Point is arr[1] which is 2. Number of
elements smaller than 2 and greater than 2 
are same.

Input  : arr[] = {1, 2, 3, 3, 3, 3, 4, 4}
Output : Equal Point does not exist.

Input : arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 6, 7}
Output : 3
First occurrence of equal point is arr[3]

Наивный подход состоит в том, чтобы взять каждый элемент и подсчитать, сколько элементов меньше этого, а затем большего элемента. Затем сравните, если оба равны или нет.

Эффективный подход заключается в создании вспомогательного массива и хранении в нем всех отдельных элементов. Если количество различных элементов четное, то Равная Точка не существует. Если count нечетно, то равная точка является средней точкой вспомогательного массива.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска равных точек в отсортированном массиве
// который может иметь много дубликатов.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает значение равной точки в отсортированном массиве arr []
// Возвращает -1, если нет равных точек.

int findEqualPoint(int arr[], int n)

{

     // Для хранения первых индексов различных элементов arr []

     int distArr[n];

  

     // Обход входного массива и сохранение индексов первого

     // вхождения отдельных элементов в distArr []

     int i = 0, di = 0;

     while (i < n)

     {

        // Этот элемент должен быть первым появлением

        // число (это проверяется нижним циклом),

        // поэтому добавляем его в отдельный массив.

        distArr[di++] = i++;

  

        // Избегать всех копий arr [i] и переходить к следующему

        // отдельный элемент.

        while (i<n && arr[i] == arr[i-1])

             i++;

     }

  

     // di теперь имеет общее количество различных элементов.

     // Если di нечетно, то равная точка существует и находится в

     // di / 2, иначе возвращает -1.

     return (di & 1)? distArr[di>>1] : -1;

}

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

int main()

{

    int arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 6, 7};

    int n = sizeof(arr)/sizeof(arr[0]);

    int index = findEqualPoint(arr, n);

    if (index != -1)

        cout << "Equal Point = " << arr[index] ;

    else

        cout << "Equal Point does not exists";

  

    return 0;

}

Джава

// Java программа для поиска равных точек в отсортированном массиве
// который может иметь много дубликатов.

  

class Test

{

    // Возвращает значение равной точки в отсортированном массиве arr []

    // Возвращает -1, если нет равных точек.

    static int findEqualPoint(int arr[], int n)

    {

         // Для хранения первых индексов различных элементов arr []

         int distArr[] = new int[n];

       

         // Обход входного массива и сохранение индексов первого

         // вхождения отдельных элементов в distArr []

         int i = 0, di = 0;

         while (i < n)

         {

            // Этот элемент должен быть первым появлением

            // число (это проверяется нижним циклом),

            // поэтому добавляем его в отдельный массив.

            distArr[di++] = i++;

       

            // Избегать всех копий arr [i] и переходить к следующему

            // отдельный элемент.

            while (i<n && arr[i] == arr[i-1])

                 i++;

         }

       

         // di теперь имеет общее количество различных элементов.

         // Если di нечетно, то равная точка существует и находится в

         // di / 2, иначе возвращает -1.

         return (di & 1)!=0 ? distArr[di>>1] : -1;

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        int arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 6, 7};

          

        int index = findEqualPoint(arr, arr.length);

        System.out.println(index != -1 ? "Equal Point = " + arr[index] 

                            : "Equal Point does not exists");

    }

}

Python 3

# Python 3 программа для поиска
# Равная точка в отсортированном
# массив, который может иметь
# много дубликатов.

  
# Возвращает значение Equal
# точка в отсортированном массиве
# обр []. Возвращает -1, если
# нет равных точек.

def findEqualPoint(arr, n):

  

    # Для хранения первых индексов

    # отдельные элементы arr []

    distArr = [0] * n

  

    # Обходной массив ввода и

    # хранить индексы первого

    # появления различных

    # элементы в distArr []

    i = 0

    di = 0

    while (i < n):

      

        # Этот элемент должен быть

        # первое появление

        # номер (это сделано

        # обязательно по нижнему циклу),

        # поэтому добавьте его в отдельный массив.

        distArr[di] = i

        di += 1

        i += 1

  

        # Избегайте всех копий

        # arr [i] и перейти к

        # следующий отдельный элемент.

        while (i < n and 

               arr[i] == arr[i - 1]):

            i += 1

      

    # di теперь имеет общее количество

    # различных элементов.

    # Если di нечетно, то равно

    # точка существует и находится в

    # di / 2, иначе возвращает -1.

    return distArr[di >> 1] if (di & 1) else -1

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

arr = [1, 2, 3, 4, 4

       5, 6, 6, 6, 7]

n = len(arr)

index = findEqualPoint(arr, n)

if (index != -1):

    print("Equal Point = "

                 arr[index])

else:

    print("Equal Point does " +

                  "not exists")

  
# Этот код добавлен
# от Smitha

C #

// C # программа для поиска Equal
// указать в отсортированном массиве
// который может иметь много дубликатов.

using System;

  

class GFG

{

    // Возвращает значение равной точки

    // в отсортированном массиве arr []

    // Возвращает -1, если есть

    // не является равной точкой.

    static int findEqualPoint(int []arr, 

                              int n)

    {

        // Для хранения первых индексов

        // отдельные элементы arr []

        int []distArr = new int[n];

      

        // Переходим массив ввода и

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

        // вхождения различных

        // элементы в distArr []

        int i = 0, di = 0;

        while (i < n)

        {

            // Этот элемент должен быть

            // первое вхождение

            // номер (это сделано

            // обязательно по нижнему циклу),

            // поэтому добавляем его в отдельный массив.

            distArr[di++] = i++;

      

            // Избегаем всех копий

            // arr [i] и перейти к

            // следующий отдельный элемент.

            while (i < n && arr[i] == arr[i - 1])

                i++;

        }

      

        // ди теперь имеет общее количество

        // различных элементов.

        // Если di нечетно, то равно

        // точка существует и находится в

        // di / 2, иначе возвращает -1.

        return (di & 1) != 0 ? 

            distArr[di >> 1] : 

                           -1;

    }

  

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

    public static void Main()

    {

        int []arr = {1, 2, 3, 4, 4, 

                     5, 6, 6, 6, 7};

          

        int index = findEqualPoint(arr, arr.Length);

        Console.Write(index != -1 ? 

                      "Equal Point = " + arr[index] : 

                      "Equal Point does not exists");

    }

}

PHP

<?php
// PHP программа для нахождения равной точки в
// отсортированный массив, который может иметь много
// дубликаты.

  
// Возвращает значение равной точки в
// отсортированный массив arr [] возвращает -1
// если нет равных точек

function findEqualPoint( $arr, $n)

{

    // Для хранения первых индексов различных

    // элементы arr []

    $distArr = array();

  

    // Обход входного массива и сохранение

    // индексы первых появлений

    // отдельные элементы в distArr []

    $i = 0; $di = 0;

      

    while ($i < $n)

    {

        // Этот элемент должен быть первым

        // вхождение числа (это

        // проверено нижним циклом),

        // поэтому добавляем его в отдельный массив.

        $distArr[$di++] = $i++;

  

        // Избегаем всех копий arr [i]

        // и перейти к следующему

        // элемент.

        while ($i < $n and 

                 $arr[$i] == $arr[$i-1])

            $i++;

    }

  

    // ди теперь имеет общее количество

    // отдельные элементы. Если ди нечетное,

    // тогда равная точка существует и

    // в di / 2, иначе вернем -1.

    return ($di & 1)? $distArr[$di>>1] : -1;

}

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

$arr = array(1, 2, 3, 4, 4, 5, 6, 6, 6, 7);

$n = count($arr);

$index = findEqualPoint($arr, $n);

if ($index != -1)

    echo "Equal Point = " , $arr[$index] ;

else

    echo "Equal Point does not exists";

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


Выход :

Equal Point = 4

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

Оптимизация пространства:
Мы можем уменьшить дополнительное пространство, обходя массив дважды, а не один раз.

  1. Подсчитайте общее количество различных элементов, выполнив обход входного массива. Пусть это количество будет distCount.
  2. Если distCount четное, вернуть -1.
  3. Если distCount нечетное, пересмотрите массив снова и остановитесь на distCount / 2 и верните этот индекс.

Спасибо Pavan Kumar JS за предложенный подход, оптимизированный для пространства.

Эта статья предоставлена Сахилом Чхаброй . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Найти равную (или среднюю) точку в отсортированном массиве с дубликатами

0.00 (0%) 0 votes