文档章节

2018.4.24 快排查找第K大

o
 osc_ns45oss7
发布于 2018/04/24 17:42
字数 584
阅读 0
收藏 0
import java.util.Arrays;

/*
    核心思想:利用快排思想,先假定从大到小排序,找枢纽,枢纽会把大小分开它的两边,当枢纽下标等于k时,
    即分了k位在它左边或右边,也就是最大或最小的排到了它的左边或右边了。那么那个枢纽就是要找的第k位了
 */
public class SearchNumData {
    /*
        n为数组长度
        k为要查找的第k大
     */
    public static int findKth(int[] a, int n, int K) {
        return findKth(a, 0, n - 1, K);
    }

    /*
           start为数组最低位下标
           end为数组最高位下标
     */
    public static int findKth(int[] a, int start, int end, int k) {
        //先进行一次快排,取得枢纽
        int pivot = partation(a, start, end);
        //pivot-start+1表示快排的前半段元素的个数(包括中轴)
        //每次划分后,大的在左边,小的在右边
        if (k == pivot - start + 1){
            return a[pivot];
        } else if (k > pivot - start + 1) {
            //说明第k大的元素在后半段,所以往后面查,start=pivot+1,k-(pivot-start+1)。往后查的还是整个数组的第k大,每次次快排枢纽的时候,已经把大的放右边了。
            return findKth(a, pivot + 1, end, k - pivot + start - 1);
        } else{
            //则第k大的元素在前半段,更新end=pivot-1
            return findKth(a, start, pivot - 1, k);
        }
    }
    //快排,找枢纽,从大到小排序
    public static int partation(int[] a, int low, int high) {
        int key = a[low];
        while (low < high) {
            while (low < high && a[high] <= key)
                high--;
            a[low] = a[high];
            while (low < high && a[low] >= key)
                low++;
            a[high] = a[low];
        }
        a[low] = key;
        return low;
    }
    
    public static void quicksort(int[] a, int low, int high) {
        if(low < high) {
            int pivot = partation(a, low, high);
            quicksort(a, low, pivot-1);
            quicksort(a, pivot+1, high);
        }
    }   
    
    public static void main(String[] args) {
        int[] array = {
                9, 1, 5, 3, 5, 2, 6, 8, 7, 6, 9, 8
        };
        System.out.println("----------原数组-----------");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
        int [] array2 = array.clone();
        int k = 4;
        int num=findKth(array,array.length,k);
        System.out.println("----------第"+k+"大-----------");
        System.out.println(num);
        System.out.println("----------处理后-----------");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
        System.out.println("----------原数组排序后-------");
//        Arrays.sort(array);
        quicksort(array,0,array.length-1);
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
        System.out.println("------------------------");
        for(int i=0;i<array2.length;i++){
            if (num==array2[i]){
                System.out.println("原数组位置-----"+i);
            }
        }
    }
}

输出:

----------原数组-----------
9 1 5 3 5 2 6 8 7 6 9 8
----------第4大-----------
8
----------处理后-----------
9 9 8 8 7 6 6 5 5 3 2 1
----------原数组排序后-------
9 9 8 8 7 6 6 5 5 3 2 1
------------------------
原数组位置-----7
原数组位置-----11

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Vue-插槽slot/具名插槽

插槽的基本使用: <div id="app"> <cpn> <span>我是替换slot的元素1</span> </cpn>------------------------------------- <cpn2> <span>......

心田已荒
27分钟前
12
0
标准Android按钮具有不同的颜色 - Standard Android Button with a different color

问题: I'd like to change the color of a standard Android button slightly in order to better match a client's branding. 我想稍微更改标准Android按钮的颜色,以便更好地匹配客户的品......

技术盛宴
45分钟前
24
0
如何在Ruby中生成随机字符串 - How to generate a random string in Ruby

问题: I'm currently generating an 8-character pseudo-random uppercase string for "A" .. "Z": 我目前正在为“ A” ..“ Z”生成一个8个字符的伪随机大写字符串: value = ""; 8.times{......

法国红酒甜
今天
20
0
原价500元的认证证书,限时免费考取!

本文作者:y****n 百度云智学院致力于为百度ABC战略(人工智能、大数据、云计算)提供人才生态体系建设,包括基于百度ABC、IoT的课程体系,整合百度优势技术能力的深度学习技术、Apollo无人车...

百度开发者中心
昨天
17
0
在virtualenv中使用Python 3 - Using Python 3 in virtualenv

问题: Using virtualenv , I run my projects with the default version of Python (2.7). 使用virtualenv ,我使用默认版本的Python(2.7)运行项目。 On one project, I need to use Pyth......

富含淀粉
今天
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部