Рубрики

Найти точку разбиения в массиве

Дан несортированный массив целых чисел. Найдите такой элемент, чтобы все элементы слева были меньше, а справа больше. Выведите -1, если такого элемента не существует.

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

Примеры :

Input :  A[] = {4, 3, 2, 5, 8, 6, 7}  
Output : 5 

Input : A[] = {5, 6, 2, 8, 10, 9, 8} 
Output : -1

Простое решение принимает O (n 2 ). Идея состоит в том, чтобы выбрать каждый элемент массива один за другим, и для каждого элемента мы должны проверить, что он больше, чем все элементы с левой стороны, и меньше, чем все элементы с правой стороны.

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

C ++

// Простая программа на C ++ для поиска точки разбиения в
// массив
#include <bits/stdc++.h>

using namespace std;

  
// Печатает такой элемент, как все элементы слева
// меньше и все элементы справа больше.

int FindElement(int A[], int n)

{

    // пройти элементы массива

    for (int i = 0; i < n; i++) {

        // Если мы нашли, что такое число

        int flag = 0;

  

        // проверка Все элементы слева меньше

        for (int j = 0; j < i; j++)

            if (A[j] >= A[i]) {

                flag = 1;

                break;

            }

  

        // проверка Все элементы справа от него больше

        for (int j = i + 1; j < n; j++)

            if (A[j] <= A[i]) {

                flag = 1;

                break;

            }

  

        // Если флаг == 0 означает, что мы нашли это число

        if (flag == 0)

            return A[i];

    }

    return -1;

}

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

int main()

{

    int A[] = { 4, 3, 2, 5, 8, 6, 7 };

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

    cout << FindElement(A, n) << endl;

    return 0;

}

Джава

// Простая Java-программа для поиска
// точка разбиения в массиве

import java.io.*;

  

class GFG {

  

    // Печатает такой элемент, как все элементы

    // слева меньше и все элементы

    // справа больше.

    static int FindElement(int[] A, int n)

    {

        // пройти элементы массива

        for (int i = 0; i < n; i++) {

              

            // Если мы нашли, что такое число

            int flag = 0;

  

            // проверяем все элементы на

            // слева меньше

            for (int j = 0; j < i; j++)

                if (A[j] >= A[i]) {

                    flag = 1;

                    break;

                }

  

            // проверяем все элементы на

            // его право больше

            for (int j = i + 1; j < n; j++)

                if (A[j] <= A[i]) {

                    flag = 1;

                    break;

                }

  

            // Если флаг == 0 указывает на то, что мы

            // нашел это число

            if (flag == 0)

                return A[i];

        }

        return -1;

    }

  

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

    static public void main(String[] args)

    {

        int[] A = {4, 3, 2, 5, 8, 6, 7};

        int n = A.length;

        System.out.println(FindElement(A, n));

    }

}

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

python3

# Простая программа на Python 3 для поиска
# точка разбиения в массиве

  
# Печатает такой элемент, как все
# элементы слева меньше и
# все элементы справа больше.

def FindElement(A, n):

      

    # элементы массива перемещения

    for i in range(0, n, 1):

          

        # Если мы нашли, что такое число

        flag = 0

  

        # проверить все элементы на своем

        # осталось меньше

        for j in range(0, i, 1):

            if (A[j] >= A[i]):

                flag = 1

                break

  

        # проверить все элементы на своем

        # Право больше

        for j in range(i + 1, n, 1):

            if (A[j] <= A[i]):

                flag = 1

                break

  

        # Если флаг == 0 означает, что мы нашли

        # этот номер

        if (flag == 0):

            return A[i]

  

    return -1

  
Код водителя

if __name__ == '__main__':

    A = [4, 3, 2, 5, 8, 6, 7]

    n = len(A)

    print(FindElement(A, n))

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

C #

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

using System;

  

class GFG {

  

    // Печатает такой элемент, как все

    // элементы слева меньше и все

    // элементы справа больше.

    static int FindElement(int[] A, int n)

    {

        // пройти элементы массива

        for (int i = 0; i < n; i++) {

              

            // Если мы нашли, что такое число

            int flag = 0;

  

            // проверяем все элементы на

            // слева меньше

            for (int j = 0; j < i; j++)

                if (A[j] >= A[i]) {

                    flag = 1;

                    break;

                }

  

            // проверяем все элементы на

            // его право больше

            for (int j = i + 1; j < n; j++)

                if (A[j] <= A[i]) {

                    flag = 1;

                    break;

                }

  

            // Если флаг == 0 указывает на то, что мы

            // нашел это число

            if (flag == 0)

                return A[i];

        }

        return -1;

    }

  

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

    static public void Main()

    {

        int[] A = { 4, 3, 2, 5, 8, 6, 7 };

        int n = A.Length;

        Console.WriteLine(FindElement(A, n));

    }

}

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

PHP

<?php
// Простая PHP-программа для поиска раздела
// указать в массиве

  
// Печатает такой элемент, как все элементы
// слева меньше и все элементы
// справа больше.

function FindElement($A, $n)

{

    // пройти элементы массива

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

    {

        // Если мы нашли, что такое число

        $flag = 0;

  

        // проверяем все элементы на своем

        // слева меньше

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

            if ($A[$j] >= $A[$i])

            {

                $flag = 1;

                break;

            }

  

        // проверяем все элементы на своем

        // Право больше

        for ( $j = $i + 1; $j < $n; $j++)

            if ($A[$j] <= $A[$i]) 

            {

                $flag = 1;

                break;

            }

  

        // Если флаг == 0 означает, что мы нашли

        // это число

        if ($flag == 0)

            return $A[$i];

    }

    return -1;

}

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

$A = array( 4, 3, 2, 5, 8, 6, 7 );

$n = count($A);

echo FindElement($A, $n);

  
// Этот код предоставлен
// Раджпут-Джи
?>


Выход:

5

Временная сложность: O (n 2 )

Эффективное решение занимает O (N) время.

  1. Создайте вспомогательный массив 'GE []'. GE [] должен хранить элемент, который больше, чем A [i] и находится слева от A [i].
  2. Создайте еще один вспомогательный массив 'SE []'. SE [i] должен хранить элемент, который меньше, чем A [i], и находится справа от A [i].
  3. Найти элемент в массиве, который содержит условие GE [i-1] <A [i] <SE [i + 1].

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

C ++

// Простая программа на C ++ для поиска
// точка разбиения в массиве
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает элемент, который имеет все
// элемент слева меньше и
// вправо больше

int FindElement(int A[], int n)

{

    // Создать массив 'SE []', который будет

    // сохранить меньший элемент на правой стороне.

    int SE[n];

  

    // Создать другой массив 'GE []', который будет

    // сохранить наибольший элемент на левой стороне.

    int GE[n];

  

    // инициализируем первый и последний индекс SE [], GE []

    GE[0] = A[0];

    SE[n - 1] = A[n - 1];

  

    // сохранить наибольший элемент слева направо

    for (int i = 1; i < n; i++) {

        if (GE[i - 1] < A[i])

            GE[i] = A[i];

        else

            GE[i] = GE[i - 1];

    }

  

    // сохраняем самый маленький элемент справа налево

    for (int i = n - 2; i >= 0; i--) {

        if (A[i] < SE[i + 1])

            SE[i] = A[i];

        else

            SE[i] = SE[i + 1];

    }

  

    // Теперь найти число, которое больше всех

    // элементы слева и меньше всего

    // тогда элементы справа

    for (int j = 0; j < n; j++) 

    {

        if ((j == 0 && A[j] < SE[j + 1]) || 

            (j == n - 1 && A[j] > GE[j - 1]) ||

            (A[j] < SE[j + 1] && A[j] > GE[j - 1]))

            return A[j];

    }

  

    return -1;

}

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

int main()

{

    int A[] = {4, 3, 2, 5, 8, 6, 7};

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

    cout << FindElement(A, n) << endl;

    return 0;

}

Джава

// Простая Java-программа для поиска
// точка разбиения в массиве

import java.io.*;

  

class GFG {

  

    // Возвращает элемент, который имеет все

    // элемент слева меньше

    // и справа от него больше

    static int FindElement(int[] A, int n)

    {

        // Создать массив 'SE []', который будет

        // сохранить меньший элемент на правой стороне.

        int[] SE = new int[n];

  

        // Создать другой массив 'GE []', который

        // будет хранить самый большой элемент на левой стороне.

        int[] GE = new int[n];

  

        // инициализируем первый и последний индекс SE [], GE []

        GE[0] = A[0];

        SE[n - 1] = A[n - 1];

  

        // сохранить наибольший элемент слева направо

        for (int i = 1; i < n; i++) 

        {

            if (GE[i - 1] < A[i])

                GE[i] = A[i];

            else

                GE[i] = GE[i - 1];

        }

  

        // сохраняем самый маленький элемент справа налево

        for (int i = n - 2; i >= 0; i--) 

        {

            if (A[i] < SE[i + 1])

                SE[i] = A[i];

            else

                SE[i] = SE[i + 1];

        }

  

        // Теперь найти число, которое больше всех

        // элементы слева и меньше всего

        // тогда элементы справа

        for (int j = 0; j < n; j++) 

        {

            if ((j == 0 && A[j] < SE[j + 1]) || 

                (j == n - 1 && A[j] > GE[j - 1]) ||

                (A[j] < SE[j + 1] && A[j] > GE[j - 1]))

                return A[j];

        }

  

        return -1;

    }

  

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

    static public void main(String[] args)

    {

        int[] A = {4, 3, 2, 5, 8, 6, 7};

        int n = A.length;

        System.out.println(FindElement(A, n));

    }

}

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

C #

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

using System;

  

class GFG {

  

    // Возвращает элемент, который имеет все

    // элемент слева меньше

    // и справа от него больше

    static int FindElement(int[] A, int n)

    {

        // Создать массив 'SE []', который будет

        // сохранить меньший элемент на правой стороне.

        int[] SE = new int[n];

  

        // Создать другой массив 'GE []', который будет

        // сохранить наибольший элемент на левой стороне.

        int[] GE = new int[n];

  

        // инициализируем первый и последний индекс SE [], GE []

        GE[0] = A[0];

        SE[n - 1] = A[n - 1];

  

        // сохранить наибольший элемент слева направо

        for (int i = 1; i < n; i++) 

        {

            if (GE[i - 1] < A[i])

                GE[i] = A[i];

            else

                GE[i] = GE[i - 1];

        }

  

        // сохраняем самый маленький элемент справа налево

        for (int i = n - 2; i >= 0; i--) 

        {

            if (A[i] < SE[i + 1])

                SE[i] = A[i];

            else

                SE[i] = SE[i + 1];

        }

  

        // Теперь найти число, которое больше всех

        // элементы слева и меньше всего

        // тогда элементы справа

        for (int j = 0; j < n; j++) 

        {

            if ((j == 0 && A[j] < SE[j + 1]) ||

                (j == n - 1 && A[j] > GE[j - 1]) || 

                (A[j] < SE[j + 1] && A[j] > GE[j - 1]))

                return A[j];

        }

  

        return -1;

    }

  

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

    static public void Main()

    {

        int[] A = {4, 3, 2, 5, 8, 6, 7};

        int n = A.Length;

        Console.WriteLine(FindElement(A, n));

    }

}

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

PHP

<?php
// PHP программа для поиска точки разбиения
// в массиве

  
// Печатает такой элемент, как все элементы
// слева меньше и все элементы
// справа больше.

function FindElement($A, $n)

{

    // пройти элементы массива

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

    {

  

        // Если мы нашли, что такое число

        $flag = 0;

  

        // проверяем все элементы на

        // слева меньше

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

            if ($A[$j] >= $A[$i])

            {

                $flag = 1;

                break;

            }

  

        // проверяем все элементы на

        // его право больше

        for ($j = $i + 1; $j < $n; $j++)

            if ($A[$j] <= $A[$i]) 

            {

                $flag = 1;

                break;

            }

  

        // Если флаг == 0 указывает на то, что мы

        // нашел это число

        if ($flag == 0)

            return $A[$i];

    }

    return -1;

}

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

$A = array(4, 3, 2, 5, 8, 6, 7);

$n = sizeof($A);

echo(FindElement($A, $n));

  
// Этот код добавлен
// Мукул Сингх
?>


Выход:

5

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

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

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

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

Найти точку разбиения в массиве

0.00 (0%) 0 votes