目录
例如
流程图
示例代码
参考资料
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
未排序数组中第 k 个最小/最大元素 （预期线性时间）(K'th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time))
给定一个数组和一个小于数组大小的数 k，我们需要找到数组中第 k 大的元素。已知数组中的所有元素都互不相同。
建议您先阅读以下文章，然后再阅读本文：
第k个最小元素：
C++ 第k个最小元素 C++ 第k个最小元素(K’th Smallest Element)-CSDN博客
C# 第k个最小元素 C# 第k个最小元素(K’th Smallest Element)-CSDN博客
Java 第k个最小元素 Java 第k个最小元素(K’th Smallest Element)_数组中第k小的数 java-CSDN博客
Python 第k个最小元素 Python 第k个最小元素(K’th Smallest Element)_最小的 k 个数 python代码-CSDN博客
JavaScript 第k个最小元素 JavaScript 第k个最小元素(K’th Smallest Element)-CSDN博客
例如
输入：arr[] = {7, 10, 4, 3, 20, 15}，
k = 3，
输出：7；
输入：arr[] = {7, 10, 4, 3, 20, 15}，
k = 4，
输出：10
在上面的文章(第k个最小元素)中讨论了三种不同的解决方案。本文将讨论方法 4，它主要是对上面的文章(第k个最小元素)中讨论的方法 3（快速选择）的扩展。
流程图
示例代码
// C# program of above implementation
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
static 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 last
// 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;
}
static 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
// oves all smaller element to left of it
// and greater elements to right
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);
}
// Driver Code
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));
}
}
// this code is contributed by 29AjayKumar
输出
K'th smallest element is 5
时间复杂度： O(N * log N)。
辅助空间： O(1)。
参考资料
C++ 第k个最小元素 C++ 第k个最小元素(K’th Smallest Element)-CSDN博客
C# 第k个最小元素 C# 第k个最小元素(K’th Smallest Element)-CSDN博客
Java 第k个最小元素 Java 第k个最小元素(K’th Smallest Element)_数组中第k小的数 java-CSDN博客
Python 第k个最小元素 Python 第k个最小元素(K’th Smallest Element)_最小的 k 个数 python代码-CSDN博客
JavaScript 第k个最小元素 JavaScript 第k个最小元素(K’th Smallest Element)-CSDN博客
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
