Рубрики

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

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

K'th самый маленький / самый большой элемент в несортированном массиве | Комплект 1

Для данного массива и числа 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

Мы обсудили три различных решения здесь .

В этом посте обсуждается метод 4, который в основном является расширением метода 3 (QuickSelect), описанного в предыдущем посте. Идея состоит в том, чтобы случайным образом выбрать элемент поворота. Чтобы реализовать рандомизированное разделение, мы используем случайную функцию rand (), чтобы сгенерировать индекс между l и r, поменять элемент со случайно сгенерированным индексом на последний элемент и, наконец, вызвать стандартный процесс разделения, который использует последний элемент в качестве pivot.

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

C / C ++

// C ++ реализация рандомизированного быстрого выбора
#include<iostream>
#include<climits>
#include<cstdlib>

using namespace std;

  

int randomPartition(int arr[], int l, int r);

  
// Эта функция возвращает k 'самый маленький элемент в arr [l..r], используя
// Метод быстрой сортировки. Предположение: элементы в ARR [] различны

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

{

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

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

    {

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

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

        int pos = randomPartition(arr, l, r);

  

        // Если позиция совпадает с 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;

}

  
// Стандартный процесс разбиения QuickSort (). Считает последний
// элемент в виде точки вращения и перемещает все меньшие элементы слева от него и
// большие элементы справа. Эта функция используется randomPartition ()

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

{

    int x = 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;

}

  
// Выбирает случайный элемент поворота между l и r и разделами
// arr [l..r] вокруг случайно выбранного элемента с использованием partition ()

int randomPartition(int arr[], int l, int r)

{

    int n = r-l+1;

    int pivot = rand() % n;

    swap(&arr[l + pivot], &arr[r]);

    return partition(arr, l, r);

}

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

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-программа для поиска k-го наименьшего элемента в ожидаемом
// линейное время

class KthSmallst

{

    // Эта функция возвращает k 'самый маленький элемент в arr [l..r]

    // используя метод QuickSort. Предположение: все элементы

    // В ARR [] ОТЛИЧАЮТСЯ

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

    {

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

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

        {

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

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

            int pos = randomPartition(arr, l, r);

  

            // Если позиция совпадает с 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;

    }

  

    // Служебный метод для замены arr [i] и arr [j]

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

    {

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

  

    // Стандартный процесс разбиения QuickSort (). Считает

    // последний элемент как pivot и перемещает все меньшие элементы

    // слева от него и больше элементов справа. Эта функция

    // используется randomPartition ()

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

    {

        int x = arr[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;

    }

  

    // Выбирает случайный элемент поворота между l и r и

    // разделы arr [l..r] вокруг случайно выбранных

    // элемент, использующий partition ()

    int randomPartition(int arr[], int l, int r)

    {

        int n = r-l+1;

        int pivot = (int)(Math.random()) * (n-1);

        swap(arr, l + pivot, r);

        return partition(arr, l, r);

    }

  

    // Метод драйвера для тестирования выше

    public static void main(String args[])

    {

        KthSmallst ob = new KthSmallst();

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

        int n = arr.length,k = 3;

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

                           ob.kthSmallest(arr, 0, n-1, k));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

python3

# Python3 реализация рандомизированной
# quickSelect

import random

  
# Эта функция возвращает k 'наименьшее
# элемент в arr [l..r] используя QuickSort
# основанный метод. Предположение: элементы
# В ARR [] ОТЛИЧАЮТСЯ

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

      

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

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

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

          

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

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

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

        pos = randomPartition(arr, l, r) 

  

        # Если позиция совпадает с 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

  
# Стандартный процесс разбиения QuickSort ().
# Он рассматривает последний элемент как опору и
# перемещает все меньшие элементы слева от него и
# большие элементы справа. Эта функция
# используется randomPartition ()

def partition(arr, l, r):

    x = arr[r]

    i = l

    for j in range(l, r):

        if (arr[j] <= x):

            swap(arr, i, j) 

            i += 1

    swap(arr, i, r) 

    return i

  
# Выбирает случайный элемент поворота между l и r
# и разделы arr [l..r] вокруг случайного
# выбранный элемент с использованием partition ()

def randomPartition(arr, l, r):

    n = r - l + 1

    pivot = int(random.random() % n) 

    swap(arr, l + pivot, r) 

    return partition(arr, l, r)

  
Код водителя

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

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

C #

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

using System;

  

class GFG 


// Эта функция возвращает k 'наименьшее
// элемент в arr [l..r] используя QuickSort
// основанный метод. Предположение: все элементы
// В ARR [] ОТЛИЧАЮТСЯ

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

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

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

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

    

        // Разделим массив вокруг

        // случайный элемент и получить позицию

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

        int pos = randomPartition(arr, l, r); 

  

        // Если позиция совпадает с 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; 

  
// Служебный метод для замены arr [i] и arr [j]

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

    int temp = arr[i]; 

    arr[i] = arr[j]; 

    arr[j] = temp; 

  
// Стандартный процесс разбиения QuickSort ().
// последний элемент рассматривается как точка опоры и
// перемещаем все меньшие элементы слева от него
// и больше элементов справа. Эта функция
// используется randomPartition ()

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

    int x = arr[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; 

  
// Выбирает случайный элемент поворота между
// l и r и разделы arr [l..r]
// вокруг случайно выбранного элемента
// используя partition ()

int randomPartition(int []arr, int l, int r) 

    int n = r - l + 1; 

    Random rnd = new Random();

    int rand = rnd.Next(0, 1);

    int pivot = (int)(rand * (n - 1)); 

    swap(arr, l + pivot, r); 

    return partition(arr, l, r); 

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

public static void Main() 

    GFG ob = new GFG(); 

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

    int n = arr.Length,k = 3; 

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

            ob.kthSmallest(arr, 0, n - 1, k)); 


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

PHP

<?php
// C # программа для поиска k
// элемент в ожидаемом линейном времени

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

function kthSmallest($arr, $l, $r, $k

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

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

    

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

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

        $pos = randomPartition($arr, $l, $r); 

  

        // Если позиция совпадает с 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 PHP_INT_MAX; 

  

function swap($a, $b

    $temp = $a

    $a = $b

    $b = $temp

  
// Стандартный процесс разбиения QuickSort ().
// считает последний элемент опорным
// и перемещает все меньшие элементы влево
// этого и больших элементов справа.
// Эта функция используется randomPartition ()

function partition($arr, $l, $r

    $x = $arr[$r];

    $i = $l

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

    

        if ($arr[$j] <= $x

        

            list($arr[$i], $arr[$j])=array($arr[$j],$arr[$i]);

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

            $i++; 

        

    

    list($arr[$i], $arr[$r])=array($arr[$r],$arr[$i]);

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

    return $i

  
// Выбирает случайный элемент поворота между
// l и r и разбиение arr [l..r] вокруг
// случайно выбранный элемент с использованием partition ()

function randomPartition($arr, $l, $r

    $n = $r-$l+1; 

    $pivot = rand() % $n

      

    list($arr[$l + $pivot], $arr[$r]) = 

            array($arr[$r],$arr[$l + $pivot] );

      

    // swap (& arr [l + pivot], & arr [r]);

    return partition($arr, $l, $r); 

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

    $arr = array(12, 3, 5, 7, 4, 19, 260); 

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

    $k = 3; 

    echo "K'th smallest element is " ,

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

      

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


Выход:

K'th smallest element is 5 

Сложность времени:
Наихудшая временная сложность вышеупомянутого решения — все еще O (n 2 ). В худшем случае, рандомизированная функция всегда может выбрать угловой элемент. Ожидаемая временная сложность вышеупомянутого рандомизированного QuickSelect составляет O (n), см. Книгу CLRS или видеолекцию MIT для доказательства. При анализе предполагается, что генератор случайных чисел с равной вероятностью будет генерировать любое число во входном диапазоне.

Источники:
MIT Видео лекция по статистике заказов, Медиана
Введение в алгоритмы от Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л.

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

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

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

0.00 (0%) 0 votes