Рубрики

Положение элемента после стабильной сортировки

Учитывая массив целых чисел, который может содержать повторяющиеся элементы, нам предоставляется элемент этого массива, нам нужно указать конечную позицию этого элемента в массиве, если применяется алгоритм устойчивой сортировки.

Примеры :

Input  : arr[] = [3, 4, 3, 5, 2, 3, 4, 3, 1, 5], index = 5
Output : 4
Element initial index – 5 (third 3)
After sorting array by stable sorting algorithm, we get 
array as shown below
[1(8), 2(4), 3(0), 3(2), 3(5), 3(7), 4(1), 4(6), 5(3), 5(9)]
with their initial indices shown in parentheses next to them,
Element's index after sorting = 4

Один из простых способов решения этой проблемы — использовать любой устойчивый алгоритм сортировки, такой как сортировка вставкой, сортировка слиянием и т. Д., А затем получить новый индекс данного элемента, но мы можем решить эту проблему без сортировки массива.
Поскольку положение элемента в отсортированном массиве определяется только теми элементами, которые меньше данного элемента. Мы считаем все элементы массива меньше, чем данный элемент, и для тех элементов, которые равны данному элементу, элементы, встречающиеся до того, как индекс данного элемента будет включен в число меньших элементов, это обеспечит стабильность индекса результата.
Простой код для реализации вышеуказанного подхода реализован ниже:

C / C ++

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

using namespace std;

  
// Метод возвращает позицию arr [idx] после
// выполнение стабильной сортировки по массиву

int getIndexInSortedArray(int arr[], int n, int idx)

{

    / * Количество элементов меньше текущего

        элемент плюс равный элемент происходит

        перед данным индексом * /

    int result = 0;

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

        // Если элемент меньше, то увеличить

        // меньшее количество

        if (arr[i] < arr[idx])

            result++;

  

        // Если элемент равен, то увеличить счетчик

        // только если это происходит раньше

        if (arr[i] == arr[idx] && i < idx)

            result++;

    }

    return result;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

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

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

  

    int idxOfEle = 5;

    cout << getIndexInSortedArray(arr, n, idxOfEle);

  

    return 0;

}

Джава

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

  

class ArrayIndex {

  

    // Метод возвращает позицию

    // arr [idx] после выполнения стабильной сортировки

    // в массиве

    static int getIndexInSortedArray(int arr[],

                                     int n, int idx)

    {

        / * Количество элементов меньше чем

        текущий элемент плюс равный элемент

        происходит до заданного индекса * /

        int result = 0;

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

  

            // Если элемент меньше

            // увеличиваем меньшее количество

            if (arr[i] < arr[idx])

                result++;

  

            // Если элемент равен, то увеличить

            // считать только если это происходит раньше

            if (arr[i] == arr[idx] && i < idx)

                result++;

        }

        return result;

    }

  

    // Код драйвера для тестирования вышеуказанных методов

    public static void main(String[] args)

    {

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

        int n = arr.length;

  

        int idxOfEle = 5;

        System.out.println(getIndexInSortedArray(arr,

                                                 n, idxOfEle));

    }

}

  
// Этот код предоставлен Рагхав Шармой

питон

# Программа Python для получения индекса элемента массива в
# отсортированный массив
# Метод возвращает позицию arr [idx] после
# выполнение стабильной сортировки по массиву

  

def getIndexInSortedArray(arr, n, idx):

       # Количество элементов меньше текущего

       # элемент плюс равный элемент встречается

       # перед данным индексом

    result = 0

    for i in range(n):

        # Если элемент меньше, то увеличить

        # меньшее количество

        if (arr[i] < arr[idx]):

            result += 1

   

        # Если элемент равен, тогда увеличить количество

        # только если это происходит раньше

        if (arr[i] == arr[idx] and i < idx):

            result += 1

    return result;

   
# Код драйвера для тестирования вышеуказанных методов

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

n = len(arr)

  

idxOfEle = 5

print getIndexInSortedArray(arr, n, idxOfEle)

  
# Предоставлено: Афзал Ансари

C #

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

using System;

  

class ArrayIndex {

      

    // Метод возвращает позицию

    // arr [idx] после выполнения стабильной сортировки

    // в массиве

    static int getIndexInSortedArray(int[] arr,

                                     int n, int idx)

    {

        / * Количество элементов меньше чем

        текущий элемент плюс равный элемент

        происходит до заданного индекса * /

        int result = 0;

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

              

            // Если элемент меньше

            // увеличиваем меньшее количество

            if (arr[i] < arr[idx])

                result++;

  

            // Если элемент равен, то увеличить

            // считать только если это происходит раньше

            if (arr[i] == arr[idx] && i < idx)

                result++;

        }

        return result;

    }

  

    // Код драйвера для тестирования вышеуказанных методов

    public static void Main()

    {

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

        int n = arr.Length;

  

        int idxOfEle = 5;

        Console.WriteLine(getIndexInSortedArray(arr, n, 

                                            idxOfEle));

    }

}

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

PHP

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

  
// Метод возвращает позицию
// arr [idx] после выполнения
// стабильная сортировка по массиву

function getIndexInSortedArray( $arr, $n, $idx)

{

      

    / * Количество элементов меньше

       чем текущий элемент плюс

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

       перед данным индексом * /

    $result = 0;

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

    {

          

        // Если элемент меньше

        // увеличиваем меньшее количество

        if ($arr[$i] < $arr[$idx])

            $result++;

  

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

        // увеличиваем количество, только если

        // это происходит раньше

        if ($arr[$i] == $arr[$idx] and 

                           $i < $idx)

            $result++;

    }

    return $result;

}

  

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

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

    $n =count($arr);

  

    $idxOfEle = 5;

    echo getIndexInSortedArray($arr, $n

                             $idxOfEle);

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


Выход:

4

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

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

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

Положение элемента после стабильной сортировки

0.00 (0%) 0 votes