JAVA题解 | #寻找第K大# 面试可用
寻找第K大
https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
import java.util.*; public class Solution { /** * 寻找数组中第K大的元素 *使用了快速排序的思想,在每一趟排序中,根据枢轴值的位置将数组分为两部分,并递归地在其中一部分中查找第K大的元素。 * @param a 数组 * @param n 数组长度 * @param K 第K大 * @return 第K大的元素值 */ public int findKth(int[] a, int n, int K) { // 快速排序,要求时间复杂度 O(nlogn),空间复杂度 O(1) // 向findKth的重载方法中传入第K大元素的索引n-K return findKth(a, 0, n - 1, n - K); } /** * 在指定范围内寻找第K大的元素 * * @param a 数组 * @param low 范围低位索引 * @param high 范围高位索引 * @param KIndex 第K大元素的索引 * @return 第K大的元素值 */ public int findKth(int[] a, int low, int high, int KIndex) { int pivot = a[low]; // 取待排部分的第一个元素为枢轴值 int i = low; int j = high; // 一趟快速排序 while (i < j) { while (a[j] >= pivot && i < j) { j--; } while (a[i] <= pivot && i < j) { i++; } if (i < j) { int temp = a[j]; a[j] = a[i]; a[i] = temp; } } // 将枢轴值放入正确的位置 a[low] = a[j]; a[j] = pivot; // 根据枢轴位置进行递归查找第K大元素 if (j == KIndex) { return a[j]; } else if (j > KIndex) { return findKth(a, low, j - 1, KIndex); } else { return findKth(a, j + 1, high, KIndex); } } }#java#
Java基础学习 文章被收录于专栏
Java基础学习专栏旨在帮助初学者建立Java编程的基础知识体系,涵盖语法、面向对象、集合框架等核心内容,并通过实例演示和练习加深理解。