Author |
Topic: K rank element (Read 1233 times) |
|
johny_cage
Full Member
Gender: 
Posts: 155
|
 |
K rank element
« on: Nov 24th, 2007, 1:42pm » |
 Quote  Modify
|
Given an array, find the k-th rank element. (k-th rank element = k-th element from the start in the sorted form(increasing) of the array)
O (nlogn) -- trivial
O(n) -- good
If already asked, plz forgive me. 
Although, I searched through the search option  but nowhere found this question.
|
| « Last Edit: Nov 24th, 2007, 1:43pm by johny_cage » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: K rank element
« Reply #1 on: Nov 25th, 2007, 7:10am » |
Quote Modify
|
Quote:| If already asked, plz forgive me. |
|
You're forgiven 
Quote:| Although, I searched through the search option but nowhere found this question. |
|
The search function of this forum really isn't that good, but it's commendable that you've tried, at least.
You might have better luck with the search option when you search "kth median" or "nth largest" (and possibly similar options)
Quote:| Given an array, find the k-th rank element. |
|
The idea is used/or mentioned in at least these three threads: 1, 2, 3.
|
| « Last Edit: Nov 25th, 2007, 7:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: K rank element
« Reply #2 on: Nov 26th, 2007, 2:05am » |
Quote Modify
|
on Nov 25th, 2007, 7:10am, towr wrote:
The search function of this forum really isn't that good, but it's commendable that you've tried, at least.
|
|
Better Idea would be to do a Google search
something like "wwu + kth largest"
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
nitin_162
Newbie
Gender:
Posts: 33
|
|
Re: K rank element
« Reply #3 on: Nov 28th, 2007, 2:54am » |
Quote Modify
|
Here I am not sorting an array in any case. I am recursively finding the element.
/**
* Finding the Kth rank element in a given array.
* @param arr
* @param k
* @return kth element in the sorted array but not sorting the array.
*/
static int kthElement(int[] arr, int k){
int ret = -1;
int pivot = arr[arr.length / 2];
List<Integer> lList = new ArrayList<Integer>();
List<Integer> rList = new ArrayList<Integer>();
int ele_r = rank(pivot, arr, lList, rList);
//If the computed rank is < k then recursively find the k - ele_r
if(ele_r <= k){
if(ele_r == k){
return arr[ele_r-1];
}
ret = kthElement(popArr(rList), k - ele_r);
} else {
ret = kthElement(popArr(lList), k);
}
return ret;
}
/**
* List to Array of Integers.
* @param list
* @return
*/
static int[] popArr(List<Integer> list) {
int[] arr = new int[list.size()];
for(int i=0; i < list.size(); i++){
arr[i] = list.get(i);
}
return arr;
}
/**
* Computing the element rank in a given array.
* @param num
* @param arr
* @return rank of an element.
*/
static int rank(int num, int[] arr, List<Integer> lList, List<Integer> rList){
int rank = 0;
for(int i=0; i < arr.length; i++){
if(arr[i] < num){
rank++;
lList.add(arr[i]);
}else {
if(arr[i] != num)
rList.add(arr[i]);
}
}
return rank+1;
}
|
|
IP Logged |
|
|
|
nitin_162
Newbie
Gender:
Posts: 33
|
|
Re: K rank element
« Reply #4 on: Nov 28th, 2007, 2:56am » |
Quote Modify
|
The idea behind the above algo is :
Given an element x ∈ S, we can answer the following query in n − 1 comparisons
Is x the k-th element or is x larger than the k-th element or is x smaller
than the k-th element ?
This is easily done by comparing x with all elements in S −{x} and finding the rank
of x. Using an arbitrary element x as a filter, we can subsequently confine our search
for the k-th element to either
(i) S> = {y ∈ S − {x}|y > x} if R(x, S) < k or
(ii) S< = {y ∈ S − {x}|y < x} if R(x, S) > k
In the fortuitous situation, R(x, S) = k,x is the required element. In case 1, we must
find k′-th element in S> where k′ = k − R(x, S).
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: K rank element
« Reply #5 on: Nov 29th, 2007, 1:48am » |
Quote Modify
|
What is this ∈ ?
|
|
IP Logged |
|
|
|
nitin_162
Newbie
Gender:
Posts: 33
|
|
Re: K rank element
« Reply #6 on: Nov 29th, 2007, 2:02am » |
Quote Modify
|
Sorry it is written by mistake.
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: K rank element
« Reply #7 on: Nov 29th, 2007, 2:25am » |
Quote Modify
|
on Nov 29th, 2007, 2:02am, nitin_162 wrote:| Sorry it is written by mistake. |
|
just correct the explanation, so that we can easily go through it.
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: K rank element
« Reply #8 on: Nov 29th, 2007, 2:53am » |
Quote Modify
|
Consider the first element of the array as the pivot (say p). Partition the array on p. If the index of p after partitioning is less than k, repeat the partitioning on the right of p. Otherwise do it on the left of p.
|
|
IP Logged |
All signatures are false.
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: K rank element
« Reply #9 on: Nov 29th, 2007, 3:27am » |
Quote Modify
|
@gotit
please elaborate your answer, with an example.
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: K rank element
« Reply #10 on: Nov 29th, 2007, 3:53am » |
Quote Modify
|
I assume array indexing starts from 1. Say you have to find the 4th rank element.
Original array:17,2,16,31,19,27,64. Pivot:17
After partitioning on 17:16,2,17,31,19,27,64
Now the index of 17 is 3 which is smaller than 4. This means that the 4th largest element must be on the right of 17 as all elements to the left are smaller than 17. So we branch to the right and again do the partitioning for that subarray.
Continue doing this partitioning until one of the pivots comes in the 4th index of the array.
|
|
IP Logged |
All signatures are false.
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: K rank element
« Reply #11 on: Nov 29th, 2007, 4:03am » |
Quote Modify
|
Please explain on the following array,
n = 7
Array is : 17, 2, 4, 31, 19, 1, 3
|
|
IP Logged |
|
|
|
Tenaliram
Newbie
Posts: 5
|
|
Re: K rank element
« Reply #12 on: Nov 29th, 2007, 5:43am » |
Quote Modify
|
You hav array given as
17, 2, 4, 31, 19, 1, 3
Consider you want to find the 4th element
now take 17 as a pivot element.
and partition the array as follows
2, 4, 1, 3, 17, 31, 19
compare the index of 17 i.e. 5 with desired index i.e. 4.
Now we can say that desired element will lie in the left of pivot element .
hence we will partition the left part of the array again with 2 as pivot element.
1, 2, 4,3,17,31,19
again compare index of 2 with 4 .We can say that the desired index value will lie on right of pivot elemnet.
Partitioning right of 2 again by taking 4 as a pivot element..
1,2,3, 4 17,31,19
Now compare the index of pivot element (4) which is 4 and we also desired fourth index value and hence we will stop here.
So the desired 4 th elemnt of the sorted array will be 4.
BTW nice Algo "GOT_IT"
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: K rank element
« Reply #13 on: Nov 29th, 2007, 6:02am » |
Quote Modify
|
on Nov 29th, 2007, 5:43am, Tenaliram wrote:
This is the standard algo for finding the kth rank element in an array. Its not something I have developed on my own.
|
|
IP Logged |
All signatures are false.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print