Рубрики

K'th самый маленький / самый большой элемент в несортированном массиве | Набор 3 (наихудший случай линейного времени)

Мы рекомендуем читать следующие посты в качестве предварительного условия этого поста.

K'th самый маленький / самый большой элемент в несортированном массиве | Комплект 1
K'th самый маленький / самый большой элемент в несортированном массиве | Набор 2 (ожидаемое линейное время)

Для данного массива и числа k, где k меньше размера массива, нам нужно найти k-й наименьший элемент в данном массиве. Дано, что все элементы массива различны.

Примеры:

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 4
Output: 10

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

Ниже приводится полный алгоритм.

kthSmallest(arr[0..n-1], k)
1) Divide arr[] into ⌈n/5⌉ groups where size of each group is 5 except possibly the last group which may have less than 5 elements.

2) Sort the above created ⌈n/5⌉ groups and find median of all groups. Create an auxiliary array ‘median[]’ and store medians of all ⌈n/5⌉ groups in this median array.

// Recursively call this method to find median of median[0..⌈n/5⌉-1]
3) medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

4) Partition arr[] around medOfMed and obtain its position.
pos = partition(arr, n, medOfMed)

5) If pos == k return medOfMed
6) If pos > k return kthSmallest(arr[l..pos-1], k)
7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

В приведенном выше алгоритме последние 3 шага такие же, как в предыдущем посте . Первые четыре шага используются, чтобы получить хорошую точку для разбиения массива (чтобы убедиться, что не слишком много элементов по обе стороны от оси вращения).

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

C ++

// C ++ реализация алгоритма линейного времени наихудшего случая
// найти самый маленький элемент
#include<iostream>
#include<algorithm>
#include<climits>

  

using namespace std;

  

int partition(int arr[], int l, int r, int k);

  
// Простая функция для поиска медианы arr []. Это называется
// только для массива размером 5 в этой программе.

int findMedian(int arr[], int n)

{

    sort(arr, arr+n);  // Сортировать массив

    return arr[n/2];   // Возвращаем средний элемент

}

  
// Возвращает k'ый наименьший элемент в arr [l..r] в худшем случае
// линейное время. Предположение: все элементы в ARR [] различны

int kthSmallest(int arr[], int l, int r, int k)

{

    // Если k меньше количества элементов в массиве

    if (k > 0 && k <= r - l + 1)

    {

        int n = r-l+1; // Количество элементов в arr [l..r]

  

        // Делим arr [] на группы размером 5, вычисляем медиану

        // каждой группы и сохраняем ее в массиве median [].

        int i, median[(n+4)/5]; // Будет этаж ((n + 4) / 5) groups;

        for (i=0; i<n/5; i++)

            median[i] = findMedian(arr+l+i*5, 5);

        if (i*5 < n) // Для последней группы с менее чем 5 элементами

        {

            median[i] = findMedian(arr+l+i*5, n%5); 

            i++;

        }    

  

        // Найти медиану всех медиан, используя рекурсивный вызов.

        // Если в медиане [] есть только один элемент, то нет необходимости

        // рекурсивного вызова

        int medOfMed = (i == 1)? median[i-1]:

                                 kthSmallest(median, 0, i-1, i/2);

  

        // Разделим массив вокруг случайного элемента и

        // получить позицию элемента pivot в отсортированном массиве

        int pos = partition(arr, l, r, medOfMed);

  

        // Если позиция совпадает с k

        if (pos-l == k-1)

            return arr[pos];

        if (pos-l > k-1)  // Если позиция больше, повторить влево

            return kthSmallest(arr, l, pos-1, k);

  

        // Остальное повторяется для правого подмассива

        return kthSmallest(arr, pos+1, r, k-pos+l-1);

    }

  

    // Если k больше чем количество элементов в массиве

    return INT_MAX;

}

  

void swap(int *a, int *b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

  
// Он ищет x в arr [l..r] и разбивает массив
// вокруг х.

int partition(int arr[], int l, int r, int x)

{

    // Поиск x в arr [l..r] и перемещение его до конца

    int i;

    for (i=l; i<r; i++)

        if (arr[i] == x)

           break;

    swap(&arr[i], &arr[r]);

  

    // Стандартный алгоритм разбиения

    i = l;

    for (int j = l; j <= r - 1; j++)

    {

        if (arr[j] <= x)

        {

            swap(&arr[i], &arr[j]);

            i++;

        }

    }

    swap(&arr[i], &arr[r]);

    return i;

}

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

int main()

{

    int arr[] = {12, 3, 5, 7, 4, 19, 26};

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

    cout << "K'th smallest element is "

         << kthSmallest(arr, 0, n-1, k);

    return 0;

}

Джава

// Java реализация худшего
// случай линейного алгоритма времени
// найти самый маленький элемент

import java.util.*;

  

class GFG 

{

  
// int section (int arr [], int l, int r, int k);

  
// Простая функция для поиска медианы arr []. Это называется
// только для массива размером 5 в этой программе.

static int findMedian(int arr[], int i,int n)

{

    if(i <= n)

        Arrays.sort(arr, i, n); // Сортировать массив

    else

        Arrays.sort(arr, n, i);

    return arr[n/2]; // Возвращаем средний элемент

}

  
// Возвращает k-й наименьший элемент
// в arr [l..r] в худшем случае
// линейное время. Предположение: все
// ЭЛЕМЕНТЫ В ARR [] ОТЛИЧАЮТСЯ

static int kthSmallest(int arr[], int l, int r, int k)

{

    // Если k меньше чем

    // количество элементов в массиве

    if (k > 0 && k <= r - l + 1)

    {

        int n = r - l + 1 ; // Количество элементов в arr [l..r]

  

        // Делим arr [] на группы размером 5,

        // вычисляем медиану каждой группы

        // и сохраняем его в массиве median [].

        int i;

          

         // Будет этаж ((n + 4) / 5) groups;

        int []median = new int[(n + 4) / 5];

        for (i = 0; i < n/5; i++)

            median[i] = findMedian(arr,l + i * 5, 5);

              

        // Для последней группы с менее чем 5 элементами

        if (i*5 < n) 

        {

            median[i] = findMedian(arr,l + i * 5, n % 5); 

            i++;

        

  

        // Найти медиану всех медиан, используя рекурсивный вызов.

        // Если в медиане [] есть только один элемент, то нет необходимости

        // рекурсивного вызова

        int medOfMed = (i == 1)? median[i - 1]:

                                kthSmallest(median, 0, i - 1, i / 2);

  

        // Разделим массив вокруг случайного элемента и

        // получить позицию элемента pivot в отсортированном массиве

        int pos = partition(arr, l, r, medOfMed);

  

        // Если позиция совпадает с k

        if (pos-l == k - 1)

            return arr[pos];

        if (pos-l > k - 1) // Если позиция больше, повторить влево

            return kthSmallest(arr, l, pos - 1, k);

  

        // Остальное повторяется для правого подмассива

        return kthSmallest(arr, pos + 1, r, k - pos + l - 1);

    }

  

    // Если k больше чем количество элементов в массиве

    return Integer.MAX_VALUE;

}

  

static int[] swap(int []arr, int i, int j)

{

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

    return arr;

}

  
// Он ищет x в arr [l..r] и
// разбивает массив вокруг x.

static int partition(int arr[], int l,

                        int r, int x)

{

    // Поиск x в arr [l..r] и перемещение его до конца

    int i;

    for (i = l; i < r; i++)

        if (arr[i] == x)

        break;

    swap(arr, i, r);

  

    // Стандартный алгоритм разбиения

    i = l;

    for (int j = l; j <= r - 1; j++)

    {

        if (arr[j] <= x)

        {

            swap(arr, i, j);

            i++;

        }

    }

    swap(arr, i, r);

    return i;

}

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

public static void main(String[] args)

{

    int arr[] = {12, 3, 5, 7, 4, 19, 26};

    int n = arr.length, k = 3;

    System.out.println("K'th smallest element is "

        + kthSmallest(arr, 0, n - 1, k));

}
}

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

python3

# Python3 реализация наихудшего случая
# алгоритм линейного времени для поиска
# k'th самый маленький элемент

  
# Возвращает k'й самый маленький элемент в arr [l..r]
# в худшем случае линейное время.
# Предположение: все элементы в ARR [] различаются

def kthSmallest(arr, l, r, k): 

      

    # Если k меньше, чем число

    # элементов в массиве

    if (k > 0 and k <= r - l + 1): 

          

        # Количество элементов в arr [l..r]

        n = r - l + 1

  

        # Разделите arr [] на группы размером 5,

        # рассчитать медиану каждой группы

        # и сохранить его в массиве медианы [].

        median = []

  

        i = 0

        while (i < n // 5):

            median.append(findMedian(arr, l + i * 5, 5))

            i += 1

  

        # Для последней группы с менее чем 5 элементами

        if (i * 5 < n):

            median.append(findMedian(arr, l + i * 5

                                              n % 5))

            i += 1

  

        # Найти медиану всех медиан с помощью рекурсивного вызова.

        # Если медиана [] имеет только один элемент, то нет необходимости

        # рекурсивного вызова

        if i == 1:

            medOfMed = median[i - 1]

        else:

            medOfMed = kthSmallest(median, 0

                                   i - 1, i // 2)

  

        # Разделить массив вокруг medOfMed

        # элемент и получить позицию разворота

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

        pos = partition(arr, l, r, medOfMed)

  

        # Если позиция совпадает с k

        if (pos - l == k - 1): 

            return arr[pos] 

        if (pos - l > k - 1): # Если позиция больше,

                              # recur для левого подмассива

            return kthSmallest(arr, l, pos - 1, k) 

  

        # Остальное повторяется для правильного подмассива

        return kthSmallest(arr, pos + 1, r, 

                           k - pos + l - 1

  

    # Если k больше, чем число

    # элементов в массиве

    return 999999999999

  

def swap(arr, a, b): 

    temp = arr[a] 

    arr[a] = arr[b] 

    arr[b] = temp 

  
# Он ищет x в arr [l..r],
# и разбивает массив вокруг x.

def partition(arr, l, r, x):

    for i in range(l, r):

        if arr[i] == x:

            swap(arr, r, i)

            break

  

    x = arr[r] 

    i =

    for j in range(l, r): 

        if (arr[j] <= x): 

            swap(arr, i, j) 

            i += 1

    swap(arr, i, r) 

    return

  
# Простая функция для поиска
# медиана arr [] от индекса l до l + n

def findMedian(arr, l, n):

    lis = []

    for i in range(l, l + n):

        lis.append(arr[i])

          

    # Сортировать массив

    lis.sort()

  

    # Вернуть средний элемент

    return lis[n // 2]

  
Код водителя

if __name__ == '__main__'

  

    arr = [12, 3, 5, 7, 4, 19, 26

    n = len(arr) 

    k = 3

    print("K'th smallest element is"

           kthSmallest(arr, 0, n - 1, k)) 

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

C #

// C # реализация худшего
// случай линейного алгоритма времени
// найти самый маленький элемент

using System;

  

class GFG 

  
// int section (int arr [], int l, int r, int k);

  
// Простая функция для поиска медианы arr []. Это называется
// только для массива размером 5 в этой программе.

static int findMedian(int []arr, int i, int n) 

    if(i <= n) 

        Array.Sort(arr, i, n); // Сортировать массив

    else

        Array.Sort(arr, n, i); 

    return arr[n/2]; // Возвращаем средний элемент

  
// Возвращает k-й наименьший элемент
// в arr [l..r] в худшем случае
// линейное время. Предположение: все
// ЭЛЕМЕНТЫ В ARR [] ОТЛИЧАЮТСЯ

static int kthSmallest(int []arr, int l,

                            int r, int k) 

    // Если k меньше чем

    // количество элементов в массиве

    if (k > 0 && k <= r - l + 1) 

    

        int n = r - l + 1 ; // Количество элементов в arr [l..r]

  

        // Делим arr [] на группы размером 5,

        // вычисляем медиану каждой группы

        // и сохраняем его в массиве median [].

        int i; 

          

        // Будет этаж ((n + 4) / 5) groups;

        int []median = new int[(n + 4) / 5]; 

        for (i = 0; i < n/5; i++) 

            median[i] = findMedian(arr, l + i * 5, 5); 

              

        // Для последней группы с менее чем 5 элементами

        if (i*5 < n) 

        

            median[i] = findMedian(arr,l + i * 5, n % 5); 

            i++; 

        

  

        // Найти медиану всех медиан, используя рекурсивный вызов.

        // Если в медиане [] есть только один элемент, то нет необходимости

        // рекурсивного вызова

        int medOfMed = (i == 1)? median[i - 1]: 

                                kthSmallest(median, 0, i - 1, i / 2); 

  

        // Разделим массив вокруг случайного элемента и

        // получить позицию элемента pivot в отсортированном массиве

        int pos = partition(arr, l, r, medOfMed); 

  

        // Если позиция совпадает с k

        if (pos-l == k - 1) 

            return arr[pos]; 

        if (pos-l > k - 1) // Если позиция больше, повторить влево

            return kthSmallest(arr, l, pos - 1, k); 

  

        // Остальное повторяется для правого подмассива

        return kthSmallest(arr, pos + 1, r, k - pos + l - 1); 

    

  

    // Если k больше чем количество элементов в массиве

    return int.MaxValue; 

  

static int[] swap(int []arr, int i, int j) 

    int temp = arr[i]; 

    arr[i] = arr[j]; 

    arr[j] = temp; 

    return arr; 

  
// Он ищет x в arr [l..r] и
// разбивает массив вокруг x.

static int partition(int []arr, int l, 

                        int r, int x) 

    // Поиск x в arr [l..r] и перемещение его до конца

    int i; 

    for (i = l; i < r; i++) 

        if (arr[i] == x) 

        break

    swap(arr, i, r); 

  

    // Стандартный алгоритм разбиения

    i = l; 

    for (int j = l; j <= r - 1; j++) 

    

        if (arr[j] <= x) 

        

            swap(arr, i, j); 

            i++; 

        

    

    swap(arr, i, r); 

    return i; 

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

public static void Main(String[] args) 

    int []arr = {12, 3, 5, 7, 4, 19, 26}; 

    int n = arr.Length, k = 3; 

    Console.WriteLine("K'th smallest element is "

        + kthSmallest(arr, 0, n - 1, k)); 


  
// Этот код предоставлен Rajput-Ji

Выход:

K'th smallest element is 5

Сложность времени:
Наихудшая временная сложность описанного выше алгоритма — O (n). Давайте проанализируем все шаги.

Шаги 1) и 2) занимают время O (n), так как поиск медианы массива размера 5 занимает время O (1), и существует n / 5 массивов размера 5.
Шаг 3) занимает время T (n / 5). Шаг 4 является стандартным разделом и занимает O (n) времени.
Интересные шаги 6) и 7). Самое большее, один из них выполнен. Это рекурсивные шаги. Каков наихудший размер этих рекурсивных вызовов? Ответ — максимальное количество элементов больше, чем medOfMed (полученное на шаге 3), или максимальное количество элементов меньше, чем medOfMed.
Сколько элементов больше, чем medOfMed, а сколько меньше?
По крайней мере, половина медиан, найденных на шаге 2, больше или равна medOfMed. Таким образом, по крайней мере половина из n / 5 групп вносит 3 элемента, которые больше, чем medOfMed, за исключением одной группы, которая содержит менее 5 элементов. Следовательно, количество элементов больше, чем medOfMed, составляет не менее.

Аналогично, количество элементов, которые меньше, чем medOfMed, составляет по меньшей мере 3n / 10 — 6. В худшем случае функция повторяется не более, чем n — (3n / 10 — 6), что составляет 7n / 10 + 6 элементов.

Обратите внимание, что 7n / 10 + 6 20 20 и что любой вход из 80 или менее элементов требует времени O (1). Поэтому мы можем получить повторение

Покажем, что время выполнения линейно по подстановке. Предположим, что T (n) cn для некоторой константы c и всех n> 80. Подстановка этой индуктивной гипотезы в правую часть рекуррентности дает


T(n)  <= cn/5 + c(7n/10 + 6) + O(n)
     <= cn/5 + c + 7cn/10 + 6c + O(n)
    <= 9cn/10 + 7c + O(n)
    <= cn, 

поскольку мы можем выбрать c достаточно большим, чтобы c (n / 10 — 7) было больше, чем функция, описываемая слагаемым O (n), для всех n> 80. Таким образом, время выполнения наихудшего случая линейно (Источник: http : //staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap10.htm ).

Обратите внимание, что приведенный выше алгоритм является линейным в худшем случае, но константы очень высоки для этого алгоритма. Следовательно, этот алгоритм не работает в практических ситуациях, рандомизированный quickSelect работает намного лучше и предпочтительнее.

Источники:
MIT Видео лекция по статистике заказов, Медиана
Введение в алгоритмы от Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л.
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap10.htm

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

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

K'th самый маленький / самый большой элемент в несортированном массиве | Набор 3 (наихудший случай линейного времени)

0.00 (0%) 0 votes