当前位置:网站首页>Find the first k small element select_ k
Find the first k small element select_ k
2022-07-05 18:00:00 【Jingling cat】
preface
Don't offer Solutions for : Sort all elements first , Then I'll find , At this time, the time complexity is O(nlgn)
Fast selection algorithm - Quick select
Quick select
and Quick sort
It's all by Tony Hoare
Invented
Quick select Of The average time complexity is zero O(n)
The worst time complexity is O(n^2)
The algorithm does not use extra space ,swap Operation is inplace operation , So the space complexity is zero O(1).
Quick select
Adopt and Quick sort
Similar steps . First choose one pivot
, And then according to Each number is related to this pivot The size of the relationship
Divide the entire array into Two parts
.
that And Quick sort The difference is
,Quick select
Only consider The molecular array where the target is sought
, and Non image Quick sort And then separate the two sides
. That's why ,Quick select
take The average time complexity ranges from O(nlogn) Down to O(n)
public static int quickSelectK(int[] arr, int l, int r, int k) {
if (arr == null || arr.length == 0) {
return -1;
}
if (k > arr.length) return -1;
if (l == r) return arr[l];
int smallIndex = partitionForQuickSelect(arr, l, r);
int num = smallIndex - l + 1;
if (k == num) return arr[smallIndex];
else if (k < num) return quickSelectK(arr, l, smallIndex - 1, k);
else return quickSelectK(arr, smallIndex + 1, r, k - num);
}
private static int partitionForQuickSelect(int[] arr, int l, int r) {
int pivot = (int) (l + Math.random() * (r - l + 1));
swap(arr, pivot, r);
int less = l - 1;
for (int i = l; i < r; i++) {
if (arr[i] <= arr[r]) swap(arr, i, ++less);
}
swap(arr, less + 1, r);
return less + 1;
}
Linear time selection algorithm
Expected linear time - Randomized_Select Random partition linear selection
The input data are different .Randomized_Select
Algorithm to Fast sorting algorithm
For the model , You can ask for The... In an array k Small elements
.
Unlike quick sorting , Quick sort
Meeting Recursively handle both sides of the partition
, and Randomized_Select
Only deal with Divided side
Average time complexity : O(n+k)=O(n) ( When k More hours )
Due to the partition operation randomized_partition The limitations of , Of the selection algorithm The worst Time complexity by O(n^2)
The quick sort algorithm needs to deal with both sides of the partition recursively , And the choice algorithm is to deal with only one side .
This difference leads to differences in performance :
The expected running time of the quick sort algorithm is Θ(nlgn), The expected running time of the selection algorithm is Θ(n)
The core
:
Every time Divide the array by the hub of the quick row [ begin....mid...end ]
If target<mid
, It's in [ begin....mid-1 ] Recursive search The first k Elements
If target>mid
, It's in [ mid+1...end ] Recursive search The first k - (mid-begin+1)
Elements
public static int randomizedSelectK(int[] arr, int l, int r, int k) {
if (k > arr.length) return -1; // The first k individual Greater than The length of the array
if (l == r) return arr[l]; //l == r For example, an array with only one element ,l==r
int lessIndex = randomizedPartition(arr, l, r);
int num = lessIndex - l + 1; // Less than or equal to the last subscript of the area It is the present. [l,r] Which element of the region
if (num == k) {
// It happens to be the k individual
return arr[lessIndex];
} else if (k < num) {
// In the area less than or equal to , stay [l,lessIndex - 1] Find in the area
return randomizedSelectK(arr, l, lessIndex - 1, k);
} else {
return randomizedSelectK(arr, lessIndex + 1, r, k - num); // In greater than area , stay [lessIndex + 1,r] Find in the area , Pay attention to the last k - num
}
}
// Partition , find Less than or equal to The last subscript
public static int randomizedPartition(int[] array, int l, int r) {
int pivot = (int) (l + Math.random() * (r - l + 1)); // Find one. [l,r] The random number in
int lessIndex = l - 1; //l The previous element of
swap(array, pivot, r); // Swap with the last element
for (int i = l; i < r; i++) {
if (array[i] <= array[r]) {
// Less than or equal to
swap(array, ++lessIndex, i); // Swap with the last number smaller than the region And self increase
}
}
swap(array, lessIndex + 1, r); // Less than or equal to the next number of the zone , and r In exchange for , bring lessIndex + 1 The number of positions is less than or equal to the last number of areas
return lessIndex + 1;
}
public static void main(String[] args) {
// int[] arr = {7, 1, 3, 4, 2, 6, 2, 8, 10, 9, 5};
int[] arr = {
30, 0, 61, 34, 69, 4, 75, 67, 23, 59, 16, 41, 33, 52, 3, 51, 23, 12, 28, 24, 12, 0, 44, 45, 14, 40, 28, 8, 4, 24, 2, 98, 32, 39, 73, 26, 2, 3, 1, 59, 82, 19, 4, 39, 33, 35, 6, 89, 70, 32, 16, 24, 24, 54, 13, 27, 25, 44, 79, 1, 38, 55, 49, 9, 6, 75, 86, 7, 20, 33, 46, 77, 35, 68, 9, 14, 2, 17, 12, 52, 13, 59, 88, 71, 6, 32, 28, 49, 11, 59, 66, 4, 16, 18, 6, 63, 17, 0};
for (int j = 1; j <= arr.length; j++) {
System.out.print(randomizedSelectK(arr, 0, arr.length - 1, j) + ", ");
}
System.out.println();
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}
Use Divided into three areas partition
Fast selection algorithm ( Find the... In the array K Big element ) - It's divided into three areas
public static int randomizedSelectK(int[] arr, int l, int r, int k) {
if (k > arr.length) return -1;
if (l == r) return arr[l];
int[] p = randomizedPartition(arr, l, r); // It's divided into three areas
/** * From the first element of the equal zone to l The number of the first element in the area , Not from Smaller than the last to l The first element of * for example * item 0 1 2 2 3 4 * index 0 1 2 3 4 5 * If p = [2,3] * * k=2 when ,res Should be 1, It's time to enter if (k < lessPart) * k=3 when ,res Should be 2, It's time to enter if (k >= lessPart && k <= morePart) | The border lessPart = 3 = p[0] - l + d ==》 d = 1 * k=4 when ,res Should be 2, It's time to enter if (k >= lessPart && k <= morePart) | The border morePart = 4 = p[1] - l + c ==》 c = 1 * k=5 when ,res Should be 3, It's time to enter if (k > morePart) */
int lessPart = p[0] - l + 1;
int morePart = p[1] - l + 1;
if (k < lessPart) {
return randomizedSelectK(arr, l, p[0] - 1, k);
} else if (k > morePart) {
return randomizedSelectK(arr, p[1] + 1, r, k - morePart); // hypothesis k = 5, That should be in morePart Area find No 1 A small number ,1 = 5 - 4 = k - morePart
} else {
return arr[p[0]]; //arr[p[0]] perhaps arr[p[1]]
}
}
public static int[] randomizedPartition(int[] arr, int l, int r) {
int rand = (int) (l + Math.random() * (r - l + 1));
swap(arr, rand, r);
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) swap(arr, ++less, l++);
else if (arr[l] > arr[r]) swap(arr, --more, l);
else l++;
}
swap(arr, more, r);
return new int[]{
less + 1, more};
}
The worst case is linear time - SELECT Median linear time selection
On average, it can O(N) Complexity
and randomizedSelect equally ,select The algorithm finds the required elements by recursively dividing the input array
however , In the process of division select The algorithm can always guarantee to get a “ good ” Division
select The deterministic partition algorithm from quick sorting is also used partition , But it was modified ------ The principal component of the partition is also used as the input parameter .
adopt select Algorithm , It can be determined that one has n>1 The... In the input array of different elements p Big elements
With 5 Elements are 1 Group Divide aggregate
Find each group 5 The median of the elements
recursive select The algorithm finds the median of these median k
The time complexity of the above process is essentially 0(n) Grade
And then to k Operate for the hub Randomized Select Recursive part of the algorithm
because k The lowest lower limit of the partition can be guaranteed ( Each median ensures that half of the elements are greater than or less than it , Therefore, the median of the median is guaranteed to be as close as possible to half of the nodes that are greater than or less than ), So the algorithm is also in the worst case 0(n) Level of complexity
First step : grouping
(1) When the scale is less than a certain threshold , Directly use the sorting algorithm to return the results .
(2) When n Greater than threshold when , hold n Elements are divided into n/5 Divided three intervals , if n No 5 Multiple , Then exclude the remaining elements ( No impact , Here is just for the middle mm), Only up to 1 The group consists of the rest n%5 Elements make up .
Sort them separately
Then pick out The middle value of each group of elements
Right again All intermediate values , Recursively call This algorithm , Pick out the middle value mm,mm That is to say The middle of the middle
(3) Divide all elements into A1、A2、A3 Three groups of , Each contains Less than 、 be equal to 、 Greater than mm The elements of
The second step : Judge k stay Which group
There are three situations , Find out The first k Which of these three arrays is the small element :
a. if A1 The number of elements Greater than or equal to k , namely The first K The elements are A1 Group Inside : stay A1 in Recursive search The first k Minor elements
p<k , Then recursively call... In the low area select Find the first k Big elements
b. if A1 The number of elements Less than k , also A1 and A2 Element number The sum is greater than or equal to k, namely The first k Elements stay A2 in ,A2 in The elements are mm: return mm
p=k (p yes partition Return value ,k Is the number to choose k Big elements ), Then return to a[p] // The following code follows here
c. otherwise , The first k The elements are A3 Group : stay A3 in Recursively find the number (k-|A1、A2 Sum of elements |) Minor elements
if p>k , Recursively call in the high area select Find the first p-k Big elements
public static int select(int[] arr, int l, int r, int k) {
if (r - l < 75) {
quickSort(arr, l, r); // Sort with insert sort
return arr[l + k - 1];
}
// grouping
int group = (r - l + 5) / 5; // Each group 5 Number common group Group
for (int i = 0; i < group; i++) {
int left = l + 5 * i;
int right = (l + i * 5 + 4) > r ? r : l + i * 5 + 4; // If it exceeds the right boundary, assign a value with the right boundary
int mid = (left + right) / 2;
quickSort(arr, left, right); // Each group Sort
swap(arr, l + i, mid); // Compare the median of each group with The first i individual In exchange for
}
int pivot = select(arr, l, l + group - 1, (group + 1) / 2); // Find the median of the median
int p = partition(arr, l, r, pivot); // Use the median of the median as the reference position
int leftNum = p - l + 1; //leftNum Used to record In front of the reference position Number of elements of
if (k == leftNum)
return arr[p];
else if (k < leftNum)
return select(arr, l, p - 1, k);
else // if k Behind the reference position , Count from the back of the reference position , That is to say (k - leftNum - 1) individual
return select(arr, p + 1, r, k - leftNum - 1);
}
private static int partition(int[] array, int start, int end, int pivot) {
int smallIndex = start - 1;
swap(array, pivot, end);
for (int i = start; i <= end; i++)
if (array[i] <= array[end]) {
smallIndex++;
if (i > smallIndex)
swap(array, i, smallIndex);
}
return smallIndex;
}
边栏推荐
- Customize the theme of matrix (I) night mode
- [JMeter] advanced writing method of JMeter script: all variables, parameters (parameters can be configured by Jenkins), functions, etc. in the interface automation script realize the complete business
- Oracle recovery tools -- Oracle database recovery tool
- Sophon kg upgrade 3.1: break down barriers between data and liberate enterprise productivity
- What are the requirements for PMP certification? How much is it?
- Size_t 是无符号的
- Seven Devops practices to improve application performance
- MATLAB查阅
- VBA drives SAP GUI to realize office automation (II): judge whether elements exist
- Star Ring Technology launched transwarp Navier, a data element circulation platform, to help enterprises achieve secure data circulation and collaboration under privacy protection
猜你喜欢
随机推荐
提高應用程序性能的7個DevOps實踐
Cmake tutorial Step3 (requirements for adding libraries)
How awesome is the architecture of "12306"?
Sophon CE社区版上线,免费Get轻量易用、高效智能的数据分析工具
Abnormal recovery of virtual machine Oracle -- Xi Fenfei
VBA drives SAP GUI to realize office automation (II): judge whether elements exist
Sentinel-流量防卫兵
Simple query cost estimation
检查命名空间和类
GIMP 2.10教程「建议收藏」
ELK日志分析系统
ISPRS2022/云检测:Cloud detection with boundary nets基于边界网的云检测
Leetcode daily practice: rotating arrays
Sophon base 3.1 launched mlops function to provide wings for the operation of enterprise AI capabilities
[TestLink] testlink1.9.18 solutions to common problems
GFS distributed file system
Leetcode daily question: the first unique character in the string
Customize the theme of matrix (I) night mode
Matlab reference
ISPRS2020/云检测:Transferring deep learning models for cloud detection between Landsat-8 and Proba-V