目录
例如
流程图
示例代码
参考资料
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
未排序数组中第 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（快速选择）的扩展。
流程图
示例代码
// Java program of above implementation
import java.util.Random;
public 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 (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 number of elements in array
return Integer.MAX_VALUE;
}
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 moves 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().nextInt(n);
swap(arr, l + pivot, r);
return partition(arr, l, r);
}
// Driver program to test above methods
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));
}
}
/*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博客
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
