企业官网建设流程全解析

目录

例如

流程图

示例代码

参考资料

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。

未排序数组中第 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博客

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。