Рубрики

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), описанного в предыдущем посте.

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 (). Считает последний
// элемент как опорный элемент и перемещает все меньшие элементы слева от него
// и больше элементов справа

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;

}

  

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-программа вышеуказанной реализации

import java.util.Random;

  

public class GFG {

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

    static 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;

    }

  

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

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

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

    static 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;

    }

  

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

        int n = r - l + 1;

        int pivot = new Random().nextInt(1);

        swap(arr, l + pivot, r);

        return partition(arr, l, r);

    }

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

    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 реализация вышеуказанной реализации

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

from random import randint

  

def randomPartition(arr, l, r):

    n = r - l + 1

    pivot = randint(1, 100) % n

    arr[l + pivot], arr[r] = arr[l + pivot], arr[r]

    return partition(arr, l, r)

  

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

  

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

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

    if (k > 0 and 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 10**9

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

def partition(arr, l, r):

    x = arr[r]

    i = l

    for j in range(l, r):

        if (arr[j] <= x):

            arr[i], arr[j] = arr[j], arr[i]

            i += 1

  

    arr[i], arr[r] = arr[r], arr[i]

    return i

  
Код водителя

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

  
# Этот код предоставлен Мохитом Кумаром

C #

// C # программа вышеуказанной реализации

using System;

  

class GFG 

  
// Эта функция возвращает 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 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; 

  

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

    int temp = arr[i]; 

    arr[i] = arr[j]; 

    arr[j] = temp; 

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

static 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; 

  

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

    int n = r - l + 1; 

    int pivot = new Random().Next(1); 

    swap(arr, l + pivot, r); 

    return partition(arr, l, r); 

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

public static void Main()

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


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


Выход:

K'th smallest element is 5


Ссылки:

http://espressocode.top/kth-smallestlargest-element-unsorted-array/

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

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

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

0.00 (0%) 0 votes