Modify the algorithm to solve the problem of finding the k-th largest number in

Question

Modify the algorithm to solve the problem of finding the k-th largest number in array A, 1kn, without sorting the entire array. Partsof the algorithm are given below. Fill in the blanks.

                 Select-k-th-largest(A: Array [1..n] of numbers)

                 1               for _____________________

                 2                                 ________________

                 3                                 for _____________________

                 4                                                   if _______________ then ___________

                 5                                 if position i then

                 6                                                   temp=A[i]

                 7                                                   A[i]=A[position]

                 8                                                   A[position]=temp

Explanation / Answer

public int findKthLargest(int[] nums, int k) { if (k < 1 || nums == null) { return 0; } return getKth(nums.length - k +1, nums, 0, nums.length - 1); } public int getKth(int k, int[] nums, int start, int end) { int pivot = nums[end]; int left = start; int right = end; while (true) { while (nums[left] left) { right--; } if (left == right) { break; } swap(nums, left, right); } swap(nums, left, end); if (k == left + 1) { return pivot; } else if (k

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.