首页 > 代码库 > 寻找第k个最大数
寻找第k个最大数
寻找第k个最大数,当然可用来求中值。
采用减治方法,将数组分为两个部分,与寻找值位置比较,类似二分法。重点理解当寻找结果在后半段时候,key值保持不变,《算法设计与分析基础》讲是右边数组的q-key个最大数,对于整个数组来书还是最第key个最大数。
import java.util.Scanner; public class FindKMax { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); // int n=scanner.nextInt(); // int a[]=new int [n]; // for (int i = 0; i < a.length; i++) { // a[i]=scanner.nextInt(); // } int n=9; int a[]={4,1,10,9,7,12,8,2,15}; // int n=7; // int a[]={4,3,2,1,6,7,5}; int key=scanner.nextInt(); if (key<=0||key>n) { System.out.println("Wrong input!"); return; } findKMax(a, 0, n-1, key-1); } public static void findKMax(int a[], int p, int e, int key) { if (p<=e) { int q=partion(a, p, e); if (key==q){ System.out.println(a[q]); } else if (key>q) { findKMax(a, q+1, e, key);//very important understand ! } else { findKMax(a, p, q-1, key); } } } public static int partion(int a[], int p, int e)// the last is the compare Value { int x=a[e]; int j=p-1; for (int i = p; i < e; i++) { if (a[i]<x) { j++; swap(a, i, j); } } swap(a, e, j+1); return j+1; } public static int partition(int a[], int p, int e)//the first is the compare Value { int x=a[p]; int j=e+1; for (int i = e; i >p; i--) { if (a[i]>x) { j--; swap(a, i, j); } } swap(a, p, j-1); return j-1; } public static void swap(int a[], int i, int j) { int t=a[i]; a[i]=a[j]; a[j]=t; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。