The implementation of the KTH largest number in an array
- 2020-04-01 23:42:23
- OfStack
Problem: there is an array of size n, A[0,1,2... n-1], find the KTH largest number.
This problem is a classic one, which is presented as a separate section in the introduction to algorithms. Moreover, its solution makes good use of the idea of divide and conquer and controls the time complexity at O(n).
The problem can also be deformed as: there is an array of size of n, A[0,1,2...,n-1], where the first k of the number.
A word difference, the original problem is "the KTH big", the deformation problem is "the k big", but the average time complexity can be controlled in O(n), which can not help but make people secretly amazing.
Let's first analyze the original problem: we have an array of size n, A[0,1,2... n-1], and find the KTH largest number.
We take exception to first, k = 1, it is the largest number, as long as the scan again array can determine the value, if k = 2, the scanning array can determine the second-largest number of both sides, and so on, the time complexity is O (k * n), if n and k are an order of magnitude, the time complexity is O (n * n), obviously not the optimal solution.
Considering the divide-and-conquer method, the difficulty lies in how to decompose the problem into two subproblems.
The most basic step of quicksort:
Pick a random number x, swap it with the end of the array, then swap the smaller number to the front and the larger number to the back.
This step decomposes the quicksort problem of an array into a sort problem of two subarrays, and now we can solve the problem of taking the KTH largest number.
Set the following table of the array to start at 0 and end at n-1.
1. Pick a random number and swap it with the end element of the array.
A) Independence idx = rand (0, n - 1); Generate random Numbers between [0,n-1].
B) Swap (array [independence idx], array [] n - 1);
2. Use the trailing element x to swap the number smaller than x to the front and the number larger than x to the back, and return the position mid of x in the array at this time.
3, if mid==n-k, then return the value, this is the KTH largest number.
If the mid > N minus k, so the KTH largest number is in the left half array, and in the left half array is the k-(n-mid) largest number.
If the mid < N minus k, so the KTH largest number is in the right half array, and it's still the KTH number.
This problem is a classic one, which is presented as a separate section in the introduction to algorithms. Moreover, its solution makes good use of the idea of divide and conquer and controls the time complexity at O(n).
The problem can also be deformed as: there is an array of size of n, A[0,1,2...,n-1], where the first k of the number.
A word difference, the original problem is "the KTH big", the deformation problem is "the k big", but the average time complexity can be controlled in O(n), which can not help but make people secretly amazing.
Let's first analyze the original problem: we have an array of size n, A[0,1,2... n-1], and find the KTH largest number.
We take exception to first, k = 1, it is the largest number, as long as the scan again array can determine the value, if k = 2, the scanning array can determine the second-largest number of both sides, and so on, the time complexity is O (k * n), if n and k are an order of magnitude, the time complexity is O (n * n), obviously not the optimal solution.
Considering the divide-and-conquer method, the difficulty lies in how to decompose the problem into two subproblems.
The most basic step of quicksort:
Pick a random number x, swap it with the end of the array, then swap the smaller number to the front and the larger number to the back.
This step decomposes the quicksort problem of an array into a sort problem of two subarrays, and now we can solve the problem of taking the KTH largest number.
Set the following table of the array to start at 0 and end at n-1.
1. Pick a random number and swap it with the end element of the array.
A) Independence idx = rand (0, n - 1); Generate random Numbers between [0,n-1].
B) Swap (array [independence idx], array [] n - 1);
2. Use the trailing element x to swap the number smaller than x to the front and the number larger than x to the back, and return the position mid of x in the array at this time.
3, if mid==n-k, then return the value, this is the KTH largest number.
If the mid > N minus k, so the KTH largest number is in the left half array, and in the left half array is the k-(n-mid) largest number.
If the mid < N minus k, so the KTH largest number is in the right half array, and it's still the KTH number.
#include "iostream"
using namespace std;
int random_partion(int *p, int n)
{
int idx=rand()%n;
swap(p[idx], p[n-1]);
int i=-1; //I represents the position of the last element less than p[n-1]
int j=0; //J is used to scan the array
for(j=0; j<n; j++)
{
//Swap the number less than p[n-1] to the first half
if(p[j]<p[n-1])
{
swap(p[++i], p[j]);
}
}
swap(p[++i], p[n-1]);
return i;
}
int getMaxK(int *p, int n, int k)
{
int mid;
if(k<=0)
return -1;
if(n<k)
return -1;
mid=random_partion(p, n); //Divide the original array once
if(mid == n-k) //If mid==n-k, then return that value, that's the KTH largest number
return p[mid];
else if(mid<n-k)
return getMaxK(p+mid+1, n-mid-1, k); //If mid<N minus k, so the KTH largest number is in the right half array, and it's still the KTH largest number
else
return getMaxK(p, mid, k-(n-mid)); //If mid> N minus k, so the KTH largest number is in the left half array, and in the left half array is the k-(n-mid) largest number
}
int main(void)
{
int num,a[] = {12012, 3, 945, 965, 66, 232, 65, 7, 8, 898, 56, 878, 170, 13, 5};
num=getMaxK(a, 15, 4);
printf("%dn",num);
system("pause");
return 0;
}