Please finish this code. Thank you! import java.util.Arrays; import java.util.Co
ID: 3874779 • Letter: P
Question
Please finish this code. Thank you!
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class KthLargest {
/**
* Suppose you have a group of N numbers and would like to
* determine the kth largest. This is known as the selection problem.
*
* One way to solve this problem would be to read the N numbers into an
* array, sort the array in decreasing order by some simple algorithm
* such as bubblesort, and then return the element in position k.
*/
public static int kthLargest1(int[] a, int k) {
assert a != null;
int n = a.length;
assert n > 0 && k <= n;
Integer[] b = new Integer[n];
for (int i = 0; i < n; i++)
b[i] = a[i];
Arrays.sort(b, new Comparator() {
public int compare(Integer x, Integer y) {
return y.compareTo(x);
}
});
return b[k - 1];
}
/**
* A somewhat better algorithm might be to read the first
* k elements into an array and sort them (in decreasing order). Next,
* each remaining element is read one by one. As a new element arrives,
* it is ignored if it is smaller that the kth element in the array.
* Otherwise, it is placed in its correct spot in the array, bumping
* one element out of the array. When the algorithm ends, the element
* in the kth position is returned as the answer.
*/
public static int kthLargest2(int[] a, int k) {
// TODO
return 0;
}
public static void main(String[] args) {
// If you've enabled asserts properly, the following will fail.
assert true == false; // Delete this once you know assert works.
int[] a, b;
a = new int[] { 8, 7, -3, 9, 2, 1, -5, 4, 12, -2 };
b = new int[] { 12, 9, 8, 7, 4, 2, 1, -2, -3, -5 };
for (int i = 0; i < a.length; i++)
assert kthLargest1(a, i + 1) == b[i];
System.out.println("kthLargest1 passes basic checks!");
for (int i = 0; i < a.length; i++)
assert kthLargest2(a, i + 1) == b[i];
System.out.println("kthLargest2 passes basic checks!");
// TODO: Conduct your timing experiments here.
}
}
Explanation / Answer
Given below is the code for the question.
Please don't forget to rate the answer if it was helpful. Thank you
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class KthLargest {
/**
* Suppose you have a group of N numbers and would like to
* determine the kth largest. This is known as the selection problem.
*
* One way to solve this problem would be to read the N numbers into an
* array, sort the array in decreasing order by some simple algorithm
* such as bubblesort, and then return the element in position k.
*/
public static int kthLargest1(int[] a, int k) {
assert a != null;
int n = a.length;
assert n > 0 && k <= n;
Integer[] b = new Integer[n];
for (int i = 0; i < n; i++)
b[i] = a[i];
Arrays.sort(b, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
return y.compareTo(x);
}
});
return b[k - 1];
}
/**
* A somewhat better algorithm might be to read the first
* k elements into an array and sort them (in decreasing order). Next,
* each remaining element is read one by one. As a new element arrives,
* it is ignored if it is smaller that the kth element in the array.
* Otherwise, it is placed in its correct spot in the array, bumping
* one element out of the array. When the algorithm ends, the element
* in the kth position is returned as the answer.
*/
public static int kthLargest2(int[] a, int k) {
assert a != null;
int n = a.length;
assert n > 0 && k <= n;
Integer[] b = new Integer[k];
for (int i = 0; i < k; i++)
b[i] = a[i];
Arrays.sort(b, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
return y.compareTo(x);
}
});
for(int i = k; i < n; i++)
{
int val = a[i];
if(val > b[k-1]) //if the new element to insert is >= the kth largest
{
//find the correct place for the element to be inserted
int pos = 0;
for(; pos < k; pos++)
{
if(val > b[pos])
break;
}
//shift all elements to right by 1 position
for(int j = k-1; j > pos; j--)
b[j] = b[j-1];
b[pos] = val;
}
}
return b[k-1];
}
public static void main(String[] args) {
// If you've enabled asserts properly, the following will fail.
assert true == false; // Delete this once you know assert works.
int[] a, b;
a = new int[] { 8, 7, -3, 9, 2, 1, -5, 4, 12, -2 };
b = new int[] { 12, 9, 8, 7, 4, 2, 1, -2, -3, -5 };
for (int i = 0; i < a.length; i++)
assert kthLargest1(a, i + 1) == b[i];
System.out.println("kthLargest1 passes basic checks!");
for (int i = 0; i < a.length; i++)
assert kthLargest2(a, i + 1) == b[i];
System.out.println("kthLargest2 passes basic checks!");
//Timing test
int n = 10000;
int k = 10;
for(int i = 1; i <=3 ;i++)
{
System.out.println("Testing for n = " + n +", finding " + k + "th largest");
int[] arr = new int[n];
for(int j = 0; j < n; j++)
arr[j] = (int)(Math.random() * 10000);
long start = System.currentTimeMillis();
int kth = kthLargest1(arr, k);
long end = System.currentTimeMillis();
long elapsed = end -start;
System.out.println(" kthLargest1 took " + elapsed + " ms");
start = System.currentTimeMillis();
kth = kthLargest2(arr, k);
end = System.currentTimeMillis();
elapsed = end -start;
System.out.println(" kthLargest2 took " + elapsed + " ms ");
n *= 2;
}
}
}
output
======
kthLargest1 passes basic checks!
kthLargest2 passes basic checks!
Testing for n = 10000, finding 10th largest
kthLargest1 took 54 ms
kthLargest2 took 6 ms
Testing for n = 20000, finding 10th largest
kthLargest1 took 63 ms
kthLargest2 took 6 ms
Testing for n = 40000, finding 10th largest
kthLargest1 took 137 ms
kthLargest2 took 8 ms