找出数组中第k大的数

╰半夏微凉° 2024-04-17 14:47 72阅读 0赞

package com.threeTop.www;
    
    /**
     * 找出数组中第k大的数
     * @author wjgs
     *
     */
    public class FindK {
    	public static void find(int[] array, int begin, int end, int k) {
    		int i = partition(array, begin, end);
    		if (i + 1 > k) {
    			// 左半部分,递归查找
    			find(array, begin, i - 1, k);
    		} else if (i + 1 < k) {
    			// 右半部分,递归查找
    			find(array, i + 1, end, k);
    		} else {
    			System.out.println("找到了第" + k + "大的数为:" + array[i]);
    			return;
    		}
    	}
    	/**
    	 * 每轮快速排序
    	 * @param array
    	 * @param begin
    	 * @param end
    	 * @return
    	 */
    	private static int partition(int[] array, int begin, int end) {
    		if (begin < end) {
    			// 第一个数作为基准
    			int key = array[begin];
    			while (begin < end) {
    				while (begin < end && array[end] > key) {
    					end--;
    				}
    				if (begin < end) {
    					array[begin] = array[end];
    					begin++;
    				}
    				while (begin < end && array[begin] < key) {
    					begin++;
    				}
    				if (begin < end) {
    					array[end] = array[begin];
    					end--;
    				}
    			}
    			array[begin] = key;
    		}
    		return begin;
    	}
    	public static void main(String[] args) {
    		int[] array = { 1, 5, 7, 9, 2, 4, 6, 8, 10, 12, 11, 14, 15, 13 };
    		FindK.find(array, 0, array.length - 1, 8);
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，72人围观）

还没有评论，来说两句吧...

相关阅读

相关找出数组中第k大的数

package com.threeTop.www; /** * 找出数组中第k大的数 * @author wjgs ...

╰半夏微凉°/ 2024年04月17日 14:47/ 0 赞/ 73 阅读

相关快排找出第K大的数（C++实现）

算法实现： include <stdio.h> void printAll(int a[], int n){ int

蔚落/ 2024年03月16日 14:46/ 0 赞/ 58 阅读

相关 1394. 找出数组中的幸运数

在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。给你一个整数数组 `arr`，请你从中找出并返回一个幸运数。如果数组中存在多

秒速五厘米/ 2023年10月05日 19:41/ 0 赞/ 17 阅读

相关【题解】使用分治法找出第K大的数（递归+分治）

题目描述输入n个数，求其中第k小的数。（要求采用分治法完成，不建议采用完整的排序）输入要求第一行包含两个整数n和k；n<1000，1<=K<=n 第二行包

àì夳堔傛蜴生んèń/ 2023年10月01日 20:48/ 0 赞/ 23 阅读

相关找出二维数组中最大的数--C语言

找出二维数组中最大的数 include "stdafx.h" int main(int argc, char argv[]) {

系统管理员/ 2023年07月05日 10:19/ 0 赞/ 22 阅读

相关 1738. 找出第 K 大的异或坐标值

2021-05-19 LeetCode每日一题链接：[https://leetcode-cn.com/problems/find-kth-largest-xor-coo

雨点打透心脏的1/2处/ 2023年01月22日 12:53/ 0 赞/ 168 阅读

相关找出数组中的第K大的数或者第K小的数

class Solution { public: int findKthLargest(vector<int>& res, int k)

本是古典何须时尚/ 2022年12月31日 01:25/ 0 赞/ 182 阅读

相关数组中第K大的数

题目描述有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存

迈不过友情╰/ 2022年12月21日 04:51/ 0 赞/ 189 阅读

相关求一个数组中第k大的数方法

求一个数组中第k大的数，我第一印象是冒泡，因为只要冒泡k趟即可，第一趟冒泡第一大，第二次冒泡第二大，第k次冒泡第k大，时间复杂度为O(kn),n为数组长度。但是我们都知道快速排

忘是亡心i/ 2022年09月26日 02:24/ 0 赞/ 264 阅读

相关找出数组[1...n]中第k小元素

1 //问题描述：试编写一个算法，使之能够在数组L[1...n]中找出第k小的元素(即从小到大排序后处于第k个位置的元素) 2 3 includ

古城微笑少年丶/ 2022年01月08日 02:15/ 0 赞/ 265 阅读