This is the 11th day of my participation in Gwen Challenge.
Hello ah, I am gray little ape, a super will write bug program ape!
Welcome to pay attention to my column “daily Blue bridge”, the main role of this column is to share with you in recent years blue Bridge Cup provincial competition and the final and other real questions, analysis of the existing algorithm ideas, data structure and other content, to help you learn more knowledge and technology!
Title: Quicksort
The following code finds the KTH smallest element from array A []
It uses a divide-and-conquer algorithm similar to the one in quicksort, with an expected time of O(N),
Please read the source code carefully and fill in the missing underlined parts
Package 2008 Provincial competition import java.util.Random; public class Main { public static int quickSelect(int a[],int l,int r,int k) { Random rand = new Random(); int p = rand.nextInt(r-l+1) + l; int x = a[p]; int tmp = a[p]; a[p] = a[r]; a[r] = tmp; int i = l, j = r; while (i<j) { while (i<j&&a[i]<x) i++; if (i<j) { a[j] = a[i]; j--; } while (i<j&&a[j]>x) j--; if (i<j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quickSelect(_______________); Else return quickSelect(a, l, i-1, k); } public static void main(String[] args) {int a[] = {1,4,2,8,5,7}; System.out.println(quickSelect(a, 0, 5, 4)); }}Copy the code
Note: only submit missing code in underlined sections. Do not copy any existing code or symbols.
Their thinking
The basic idea of this method is that it adopts a divide-and-conquer strategy to decompose the original problem into several smaller sub-problems with similar structure to the original problem. Solve these subproblems recursively, and then combine the solutions of these subproblems into solutions of the original problem.
And then we can obviously see that the last part that fills in the blanks is a recursion, so it must be a subproblem. So if you follow the else code, you can derive the correct answer.
For the basic idea of these kinds of commonly used sorting, you can read my article: “In plain English and the interviewer pull” the basic idea of eight commonly used sorting algorithms “.
Answer source:
Package 2008 Provincial competition import java.util.Random; public class Year2018_Bt5 { public static int quickSelect(int a[],int l,int r,int k) { Random rand = new Random(); int p = rand.nextInt(r-l+1) + l; int x = a[p]; int tmp = a[p]; a[p] = a[r]; a[r] = tmp; int i = l, j = r; while (i<j) { while (i<j&&a[i]<x) i++; if (i<j) { a[j] = a[i]; j--; } while (i<j&&a[j]>x) j--; if (i<j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quickSelect(a, i + 1, r, k - i + l - 1); Else return quickSelect(a, l, i-1, k); } public static void main(String[] args) {int a[] = {1,4,2,8,5,7}; Println (quickSelect(a, 0, 5, 6)); }}Copy the code
Example output:
There are deficiencies or improvements, but also hope that small partners put forward messages, learn together!
Interested partners can pay attention to the column!
Grey ape accompany you to progress together!