Biranchi
BAN USERThis is an Order statistics problem and can be solved using Randomized Partition (which is of O(n)).
Here is the implementation in C#:
public class OrderStatistics
{
// Driver
private static void Main()
{
var arr = new[] { 6, 14, 10, 2, 8, 12, 4 };
// find 3rd largest element
var value = FindKth(arr, 3);
Console.Write(value);
Console.ReadKey();
}
public static int FindKth(int[] arr, int kth)
{
if (kth < 1 || kth > arr.Length)
{
throw new Exception("Index out of range");
}
var pos = Find(arr, kth - 1, 0, arr.Length - 1);
return arr[pos];
}
private static int Find(int[] arr, int kth, int start, int end)
{
int p = Partition(arr, start, end);
if (kth == p)
return p;
if (kth < p)
p = Find(arr, kth, start, p);
else
p = Find(arr, kth, p + 1, end);
return p;
}
private static int Partition(int[] arr, int start, int end)
{
int p = start,
i = start;
for (int j = start + 1; j <= end; j++)
{
if (arr[j] < arr[p])
{
Exchange(arr, ++i, j);
}
}
Exchange(arr, p, i);
return i;
}
private static void Exchange(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Added a few more line to have proper name for the button so that the creation can be traced back. Also, this is without jQuery.
<head>
<meta charset="utf-8" />
<title>Hydra</title>
<script>
function createButton(container, n) {
var btn = document.createElement('button');
btn.innerHTML = n;
btn.style.margin = "5px";
btn.onclick = function () { btnClick(this, container); };
container.appendChild(btn);
}
function btnClick(element, container) {
var name = element.innerText;
createButton(container, name + '.1');
createButton(container, name + '.2');
container.removeChild(element);
};
function load() {
var container = document.getElementById('containerDiv');
createButton(container, 1);
}
</script>
</head>
<body onload="load()">
<div id="containerDiv"></div>
</body>
There are 2 solutions to the problem.
- If space is not a constraint but time is, then you use the solution(Randomized Partition) that I had provided above earlier.
- now, if space is constraint, you do a trade off and use a MAX heap. yes, MAX heap and not min heap!
the approach is, if you're trying to find 4th element in a array of size 10, that means, if you sort that array, it going to be on the 4th place. (and we're not going to sort, this is just an example). That mean, this kth number is going to be the max of the kth array.
So the idea is:
- Build a kth size max heap
- run rest of the element through the 0th position of the heap.
- if the number is lesser then the 0th position of the heap, replace that at 0 position and correct the heap.
- at the end, you'll have the kth element at top of the heap.
Here is the C# implementation:
Complexity: n Log(k)
- Biranchi August 29, 2014Now the beauty of this implementation is, once you have the k capacity heap, you need to access each of the rest of the elements once only. so, you can run a stream of numbers through the heap and will have the kth number at the end. :)
Hope this helps!