หลังจากได้รับคำถามนี้แล้ว คุณจะต้องนึกถึงการเรียงลำดับก่อน หลังจากการเรียงลำดับ ให้เลือกหมายเลข K ที่ใหญ่ที่สุด การเรียงลำดับการเลือก การเรียงลำดับด่วนเป็นตัวเลือกที่ดีกว่า
เอาล่ะ เรามาทำวิธีแก้ปัญหาแรกกัน: การเรียงลำดับอย่างรวดเร็ว
รหัสมีดังนี้
คัดลอกรหัสรหัสดังต่อไปนี้:
โมฆะสาธารณะแบบคงที่ QuickSort (int [] arr, int เริ่มต้น, int end) {
ถ้า (เริ่มต้น <สิ้นสุด) {
คีย์ int = arr [เริ่มต้น];
int ขวา = เริ่มต้น;
int ซ้าย = สิ้นสุด;
ในขณะที่ (ขวา < ซ้าย) {
ในขณะที่ (ขวา <ซ้าย && arr[ซ้าย] > ปุ่ม) {
ซ้าย --;
-
ถ้า (ขวา < ซ้าย) {
arr[ขวา] = arr[ซ้าย];
-
ในขณะที่ (ขวา <ซ้าย && arr[ขวา] <= คีย์) {
ขวา++;
-
ถ้า (ขวา < ซ้าย) {
arr[ซ้าย] = arr[ขวา];
-
-
arr[ขวา] = คีย์;
QuickSort(arr, เริ่ม, ขวา-1);
QuickSort(arr, ซ้าย+1, สิ้นสุด);
-
-
หลังจากการเรียงลำดับอย่างรวดเร็ว อาร์เรย์จะเรียงตามลำดับด้านบนจากเล็กไปใหญ่ ดังนั้นผลลัพธ์ของเราจึงควรเป็นดังนี้
คัดลอกโค้ดดังนี้ int k = 4;
สำหรับ (int i=arr.length-1; i>=arr.length-k; i--) {
System.out.println(arr[i]+" ");
-
- วิธีแก้ปัญหาแรกนั้นดีอยู่แล้ว แต่มีวิธีที่ดีกว่านี้ไหม?
คำตอบคือใช่! เราสามารถเลือกการเรียงลำดับบางส่วนได้ จากนั้นเราใช้การเรียงลำดับแบบเลือกเพื่อแก้ไขปัญหานี้
รหัสมีดังนี้:
คัดลอกโค้ดดังต่อไปนี้: public static int[] selectSortK(int[] arr, int k) {
ถ้า (arr == null || arr.length == 0) {
กลับเป็นโมฆะ;
-
int[] newArr = ใหม่ int[k];
List<Integer> list = new ArrayList<Integer>();//บันทึกตัวห้อยของจำนวนสูงสุดในแต่ละครั้ง
สำหรับ (int i=0; i<k; i++) {
int maxValue = จำนวนเต็ม MIN_VALUE; // ค่าสูงสุด
int maxIndex = ฉัน;
สำหรับ (int j=0; j<arr.length; j++) {
ถ้า (arr[j] > maxValue && !list.contains(j) ) {
maxValue = arr[j];
ดัชนีสูงสุด = เจ;
-
-
if (!list.contains(maxIndex)) {//หากไม่มี ให้เพิ่มเข้าไป
list.add(maxIndex);
newArr[i] = ค่าสูงสุด;
-
-
กลับ newArr;
-