未排序数组中第K个最小/最大元素|集2（预期线性时间）-yiteyi-C++库

我们建议阅读以下文章作为这篇文章的先决条件。

null

给定一个数组和一个数字k，其中k小于数组的大小，我们需要找到给定数组中的第k个最小元素。给出了所有数组元素都是不同的。

例如：

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

我们讨论了三种不同的解决方案在这里 .

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

本文将讨论方法5，它主要是本文中讨论的方法4（QuickSelect）的扩展以前的邮递其想法是随机选择一个枢轴元素。为了实现随机划分，我们使用一个随机函数，兰德（）要在l和r之间生成索引，将随机生成的索引处的元素与最后一个元素交换，最后调用使用最后一个元素作为轴心的标准分区过程。

以下是上述随机QuickSelect的实现。

C++

                         // C++ implementation of randomized quickSelect                       
                         #include<iostream>                       
                         #include<climits>                       
                         #include<cstdlib>                       
                         using                                     namespace                                     std;                       
           
                         int                                     randomPartition(                                     int                                     arr[],                                     int                                     l,                                     int                                     r);                       
           
                         // This function returns k'th smallest element in arr[l..r] using                       
                         // QuickSort based method. ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT                       
                         int                                     kthSmallest(                                     int                                     arr[],                                     int                                     l,                                     int                                     r,                                     int                                     k)                       
                         {                       
                                                 // If k is smaller than number of elements in array                       
                                                 if                                     (k > 0 && k <= r - l + 1)                       
                                                 {                       
                                                 // Partition the array around a random element and                       
                                                 // get position of pivot element in sorted array                       
                                                 int                                     pos = randomPartition(arr, l, r);                       
           
                                                 // If position is same as k                       
                                                 if                                     (pos-l == k-1)                       
                                                 return                                     arr[pos];                       
                                                 if                                     (pos-l > k-1)                                     // If position is more, recur for left subarray                       
                                                 return                                     kthSmallest(arr, l, pos-1, k);                       
           
                                                 // Else recur for right subarray                       
                                                 return                                     kthSmallest(arr, pos+1, r, k-pos+l-1);                       
                                                 }                       
           
                                                 // If k is more than the number of elements in the array                       
                                                 return                                     INT_MAX;                       
                         }                       
           
                         void                                     swap(                                     int                                     *a,                                     int                                     *b)                       
                         {                       
                                                 int                                     temp = *a;                       
                                                 *a = *b;                       
                                                 *b = temp;                       
                         }                       
           
                         // Standard partition process of QuickSort(). It considers the last                       
                         // element as pivot and moves all smaller element to left of it and                       
                         // greater elements to right. This function is used by 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;                       
                         }                       
           
                         // Picks a random pivot element between l and r and partitions                       
                         // arr[l..r] around the randomly picked element using 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);                       
                         }                       
           
                         // Driver program to test above methods                       
                         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

                         // Java program to find k'th smallest element in expected                       
                         // linear time                       
                         class                                     KthSmallst                       
                         {                       
                                                 // This function returns k'th smallest element in arr[l..r]                       
                                                 // using QuickSort based method. ASSUMPTION: ALL ELEMENTS                       
                                                 // IN ARR[] ARE DISTINCT                       
                                                 int                                     kthSmallest(                                     int                                     arr[],                                     int                                     l,                                     int                                     r,                                     int                                     k)                       
                                                 {                       
                                                 // If k is smaller than number of elements in array                       
                                                 if                                     (k >                                     0                                     && k <= r - l +                                     1                                     )                       
                                                 {                       
                                                 // Partition the array around a random element and                       
                                                 // get position of pivot element in sorted array                       
                                                 int                                     pos = randomPartition(arr, l, r);                       
           
                                                 // If position is same as k                       
                                                 if                                     (pos-l == k-                                     1                                     )                       
                                                 return                                     arr[pos];                       
           
                                                 // If position is more, recur for left subarray                       
                                                 if                                     (pos-l > k-                                     1                                     )                       
                                                 return                                     kthSmallest(arr, l, pos-                                     1                                     , k);                       
           
                                                 // Else recur for right subarray                       
                                                 return                                     kthSmallest(arr, pos+                                     1                                     , r, k-pos+l-                                     1                                     );                       
                                                 }                       
           
                                                 // If k is more than number of elements in array                       
                                                 return                                     Integer.MAX_VALUE;                       
                                                 }                       
           
                                                 // Utility method to swap arr[i] and arr[j]                       
                                                 void                                     swap(                                     int                                     arr[],                                     int                                     i,                                     int                                     j)                       
                                                 {                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[j];                       
                                                 arr[j] = temp;                       
                                                 }                       
           
                                                 // Standard partition process of QuickSort(). It considers                       
                                                 // the last element as pivot and moves all smaller element                       
                                                 // to left of it and greater elements to right. This function                       
                                                 // is used by 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;                       
                                                 }                       
           
                                                 // Picks a random pivot element between l and r and                       
                                                 // partitions arr[l..r] arount the randomly picked                       
                                                 // element using 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);                       
                                                 }                       
           
                                                 // Driver method to test above                       
                                                 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));                       
                                                 }                       
                         }                       
                         /*This code is contributed by Rajat Mishra*/                       

Python3

                         # Python3 implementation of randomized                       
                         # quickSelect                       
                         import                                     random                       
           
                         # This function returns k'th smallest                       
                         # element in arr[l..r] using QuickSort                       
                         # based method. ASSUMPTION: ELEMENTS                       
                         # IN ARR[] ARE DISTINCT                       
                         def                                     kthSmallest(arr, l, r, k):                       
                                   
                                                 # If k is smaller than number of                       
                                                 # elements in array                       
                                                 if                                     (k >                                     0                                     and                                     k <                                     =                                     r                                     -                                     l                                     +                                     1                                     ):                       
                                   
                                                 # Partition the array around a random                       
                                                 # element and get position of pivot                       
                                                 # element in sorted array                       
                                                 pos                                     =                                     randomPartition(arr, l, r)                       
           
                                                 # If position is same as k                       
                                                 if                                     (pos                                     -                                     l                                     =                                     =                                     k                                     -                                     1                                     ):                       
                                                 return                                     arr[pos]                       
                                                 if                                     (pos                                     -                                     l > k                                     -                                     1                                     ):                                     # If position is more,                       
                                                 # recur for left subarray                       
                                                 return                                     kthSmallest(arr, l, pos                                     -                                     1                                     , k)                       
           
                                                 # Else recur for right subarray                       
                                                 return                                     kthSmallest(arr, pos                                     +                                     1                                     , r,                       
                                                 k                                     -                                     pos                                     +                                     l                                     -                                     1                                     )                       
           
                                                 # If k is more than the number of                       
                                                 # elements in the array                       
                                                 return                                     999999999999                       
           
                         def                                     swap(arr, a, b):                       
                                                 temp                                     =                                     arr[a]                       
                                                 arr[a]                                     =                                     arr[b]                       
                                                 arr[b]                                     =                                     temp                       
           
                         # Standard partition process of QuickSort().                       
                         # It considers the last element as pivot and                       
                         # moves all smaller element to left of it and                       
                         # greater elements to right. This function                       
                         # is used by 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                       
           
                         # Picks a random pivot element between l and r                       
                         # and partitions arr[l..r] around the randomly                       
                         # picked element using 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)                       
           
                         # Driver Code                       
                         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))                       
           
                         # This code is contributed by PranchalK                       

C#

                         // C# program to find k'th smallest                       
                         // element in expected linear time                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         // This function returns k'th smallest                       
                         // element in arr[l..r] using QuickSort                       
                         // based method. ASSUMPTION: ALL ELEMENTS                       
                         // IN ARR[] ARE DISTINCT                       
                         int                                     kthSmallest(                                     int                                     []arr,                                     int                                     l,                                     int                                     r,                                     int                                     k)                       
                         {                       
                                                 // If k is smaller than number                       
                                                 // of elements in array                       
                                                 if                                     (k > 0 && k <= r - l + 1)                       
                                                 {                       
                                                 // Partition the array around a                       
                                                 // random element and get position                       
                                                 // of pivot element in sorted array                       
                                                 int                                     pos = randomPartition(arr, l, r);                       
           
                                                 // If position is same as k                       
                                                 if                                     (pos-l == k - 1)                       
                                                 return                                     arr[pos];                       
           
                                                 // If position is more, recur                       
                                                 // for left subarray                       
                                                 if                                     (pos - l > k - 1)                       
                                                 return                                     kthSmallest(arr, l, pos - 1, k);                       
           
                                                 // Else recur for right subarray                       
                                                 return                                     kthSmallest(arr, pos + 1, r,                       
                                                 k - pos + l - 1);                       
                                                 }                       
           
                                                 // If k is more than number of                       
                                                 // elements in array                       
                                                 return                                     int                                     .MaxValue;                       
                         }                       
           
                         // Utility method to swap arr[i] and arr[j]                       
                         void                                     swap(                                     int                                     []arr,                                     int                                     i,                                     int                                     j)                       
                         {                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[j];                       
                                                 arr[j] = temp;                       
                         }                       
           
                         // Standard partition process of QuickSort().                       
                         // It considers the last element as pivot and                       
                         // moves all smaller element to left of it                       
                         // and greater elements to right. This function                       
                         // is used by 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;                       
                         }                       
           
                         // Picks a random pivot element between                       
                         // l and r and partitions arr[l..r]                       
                         // around the randomly picked element                       
                         // using 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);                       
                         }                       
           
                         // Driver Code                       
                         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));                       
                         }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

PHP

                         <?php                       
                         // Php program to find k'th smallest                       
                         // element in expected linear time                       
           
                         // This function returns k'th smallest                       
                         // element in arr[l..r] using QuickSort based method.                       
                         // ASSUMPTION: ELEMENTS IN ARR[] ARE DISTINCT                       
                         function                                     kthSmallest(                                     $arr                                     ,                                     $l                                     ,                                     $r                                     ,                                     $k                                     )                       
                         {                       
                                                 // If k is smaller than number of elements in array                       
                                                 if                                     (                                     $k                                     > 0 &&                                     $k                                     <=                                     $r                                     -                                     $l                                     + 1)                       
                                                 {                       
                                                 // Partition the array around a random element and                       
                                                 // get position of pivot element in sorted array                       
                                                 $pos                                     = randomPartition(                                     $arr                                     ,                                     $l                                     ,                                     $r                                     );                       
           
                                                 // If position is same as k                       
                                                 if                                     (                                     $pos                                     -                                     $l                                     ==                                     $k                                     -1)                       
                                                 return                                     $arr                                     [                                     $pos                                     ];                       
                                   
                                                 // If position is more, recur for left subarray                       
                                                 if                                     (                                     $pos                                     -                                     $l                                     >                                     $k                                     -1)                       
                                                 return                                     kthSmallest(                                     $arr                                     ,                                     $l                                     ,                                     $pos                                     -1,                                     $k                                     );                       
           
                                                 // Else recur for right subarray                       
                                                 return                                     kthSmallest(                                     $arr                                     ,                                     $pos                                     +1,                                     $r                                     ,                       
                                                 $k                                     -                                     $pos                                     +                                     $l                                     -1);                       
                                                 }                       
           
                                                 // If k is more than the number of elements in the array                       
                                                 return                                     PHP_INT_MAX;                       
                         }                       
           
                         function                                     swap(                                     $a                                     ,                                     $b                                     )                       
                         {                       
                                                 $temp                                     =                                     $a                                     ;                       
                                                 $a                                     =                                     $b                                     ;                       
                                                 $b                                     =                                     $temp                                     ;                       
                         }                       
           
                         // Standard partition process of QuickSort().                       
                         // It considers the last element as pivot                       
                         // and moves all smaller element to left                       
                         // of it and greater elements to right.                       
                         // This function is used by 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                                     ;                       
                         }                       
           
                         // Picks a random pivot element between                       
                         // l and r and partitions arr[l..r] around                       
                         // the randomly picked element using 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                                     );                       
                         }                       
           
                         // Driver program to test the above methods                       
                                                 $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                                     );                       
                                   
           
                         // This code is contributed by ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find k'th smallest element in expected                       
                         // linear time                       
           
           
                         // This function returns k'th smallest element in arr[l..r]                       
                         // using QuickSort based method. ASSUMPTION: ALL ELEMENTS                       
                         // IN ARR[] ARE DISTINCT                       
                         function                                     kthSmallest(arr,l,r,k)                       
                         {                       
                                                 // If k is smaller than number of elements in array                       
                                                 if                                     (k > 0 && k <= r - l + 1)                       
                                                 {                       
                                                 // Partition the array around a random element and                       
                                                 // get position of pivot element in sorted array                       
                                                 let pos = randomPartition(arr, l, r);                       
                                   
                                                 // If position is same as k                       
                                                 if                                     (pos-l == k-1)                       
                                                 return                                     arr[pos];                       
                                   
                                                 // If position is more, recur for left subarray                       
                                                 if                                     (pos-l > k-1)                       
                                                 return                                     kthSmallest(arr, l, pos-1, k);                       
                                   
                                                 // Else recur for right subarray                       
                                                 return                                     kthSmallest(arr, pos+1, r, k-pos+l-1);                       
                                                 }                       
                                   
                                                 // If k is more than number of elements in array                       
                                                 return                                     Integer.MAX_VALUE;                       
                         }                       
           
                         // Utility method to swap arr[i] and arr[j]                       
                         function                                     swap(arr,i,j)                       
                         {                       
                                                 let temp = arr[i];                       
                                                 arr[i] = arr[j];                       
                                                 arr[j] = temp;                       
                         }                       
           
                         // Standard partition process of QuickSort(). It considers                       
                         // the last element as pivot and moves all smaller element                       
                         // to left of it and greater elements to right. This function                       
                         // is used by randomPartition()                       
                         function                                     partition(arr,l,r)                       
                         {                       
                                                 let x = arr[r], i = l;                       
                                                 for                                     (let j = l; j <= r - 1; j++)                       
                                                 {                       
                                                 if                                     (arr[j] <= x)                       
                                                 {                       
                                                 swap(arr, i, j);                       
                                                 i++;                       
                                                 }                       
                                                 }                       
                                                 swap(arr, i, r);                       
                                                 return                                     i;                       
                         }                       
           
                         // Picks a random pivot element between l and r and                       
                         // partitions arr[l..r] arount the randomly picked                       
                         // element using partition()                       
                         function                                     randomPartition(arr,l,r)                       
                         {                       
                                                 let n = r-l+1;                       
                                                 let pivot = Math.floor((Math.random()) * (n-1));                       
                                                 swap(arr, l + pivot, r);                       
                                                 return                                     partition(arr, l, r);                       
                         }                       
           
                         let arr=[12, 3, 5, 7, 4, 19, 26];                       
                         let n = arr.length,k = 3;                       
                         document.write(                                     "K'th smallest element is "                                     +                       
                         kthSmallest(arr, 0, n-1, k));                       
           
           
           
                         // This code is contributed by rag2127                       
           
                         </script>                       

输出：

K'th smallest element is 5

时间复杂性： 上述解的最坏情况时间复杂度仍然是O（n） ^2. ).在最坏的情况下，随机函数可能总是选择一个角元素。上述随机QuickSelect的预期时间复杂度为O（n），请参见 CLRS手册或麻省理工学院视频讲座为了证明。分析中的假设是，随机数生成器同样可能生成输入范围内的任何数字。

资料来源： 麻省理工学院顺序统计视频讲座 Clifford Stein、Thomas H.Cormen、Charles E.Leiserson、Ronald L。

本文由 希瓦姆 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章