Question:Given a team of N players. How many minimum games are required to find kth best player in O(n+klog(n)) ?
let's say we want to find the largest 20 numbers from list
of 1000 numbers.
This order of this search would be:
-O(n+klogn)==>1000+20*log(1000)=1200 comparision only.
-O(nlogn)==>1000*log(1000)=10,000 comparision .
-O(kn)==>120*1000=20,000 comparision .
package sorting;
import java.util.Scanner;
public class Tournament {
static int min;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[2 * n + 1];
for (int i = n; i <= 2 * n - 1; i++) {
arr[i] = sc.nextInt();
}
min = arr[n];
for (int i = 2 * n - 2; i >= 1; i -= 2)
arr[i / 2] = max(arr[i], arr[i + 1]);
for (int a : arr)
System.out.print(a + " ");
// System.out.println("\nmax:" + arr[1]);
// System.out.println("\nmin:" + min);
System.out.println("\n Sorted array");
for (int i = 1; i <= n; i++) {
{
System.out.println(arr[1]);
getNext(arr, n, min - 1);
}
}
}
static void getNext(int arr[], int n, int min) {
// finding min. in arr
int i = 2;
for (i = 2; i <= 2 * n - 1;) {
if (arr[i] < arr[i + 1]) {
arr[i + 1] = min;
i = (i + 1) * 2;
} else {
arr[i] = min;
i = i * 2;
}
}
for (i = i / 2; i >= 1; i = i / 2) {
if (i % 2 == 0)
arr[i / 2] = max(arr[i], arr[i + 1]);
else
arr[i / 2] = max(arr[i], arr[i - 1]);
}
}
static int max(int a, int b) {
if (a > b) {
if (min > b)
min = b;
return a;
} else {
if (min > a)
min = a;
return b;
}
}
}
OUTPUT 8 8 7 5 15 1 6 9 4 0 15 15 9 8 15 6 9 8 7 5 15 1 6 9 4 0 Sorted array 15 9 8 7 6 5 4 1
public class TournamentAnotherImp {
static int b[],min=0;
public TournamentAnotherImp(int a[]) {
b = new int[2 * a.length - 1];
int j = b.length - 1;
min=a[0];
for (int i = a.length-1; i >= 0; i--) {
b[j--] = a[i];
if(a[i]= b[i - 1])
b[j--] = b[i];
else
b[j--] = b[i - 1];
i=i-2;
}
}
static void printArray()
{for(int i:b)
{System.out.print(i+" " );}
}
static int nextMax() {
int val=b[0];
for(int i=1;i< b.length;i++)
{
if(b[i]==val)
{b[i]=min;
i=i*2;
}
}
buildTree();
return val;
}
public static void main(String[] args) {
int a[] = { 8, 4, 6, 2, 1, 7, 5, 3 };
TournamentAnotherImp sm = new TournamentAnotherImp(a);
sm.printArray();
System.out.println();
for(int i=0;i< a.length;i++)
System.out.print(nextMax()+"_");System.out.println();
}
}
>OUTPUT
>8 8 7 8 6 7 5 8 4 6 2 1 7 5 3
>8_7_6_5_4_3_2_1_
