侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 101 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

算法练习(23) - 快排:顺序统计量

惊羽
2022-03-11 / 0 评论 / 0 点赞 / 465 阅读 / 731 字
温馨提示:
本文为原创作品,感谢您喜欢~

问题

找出给定数组的第x大的数

code

public class _03FindOrderXNumberTest {

    @Test
    public void findOrderXNumber_test() {
        int[]  a = {1,9,16,14,4,7,2,9,10,3};
        int orderXNumber = findOrderXNumber(a, 0, a.length - 1, 9);
        System.out.println(orderXNumber);
    }

    private int findOrderXNumber(int[] a, int p, int q, int x) {
        if(p==q){
            return a[q];
        }
        int r = partition(a,p,q);
         int k = r-p + 1;
         if(k == x){
             return a[r];
         }else if (x>k){
             return findOrderXNumber(a,r+1,q,x-k);
         }else{
             return findOrderXNumber(a,p,r-1,x);
         }
    }

    private int partition(int[] a, int p, int q) {
        int s = a[q];
        int point = p-1;
        for (int i = p; i < q; i++) {
            if(a[i] < s){
                point ++;
                int temp = a[point];
                a[point] = a[i];
                a[i] = temp;
            }
        }
        int temp = a[point+1];
        a[point +1] = a[q];
        a[q] = temp;
        return point +1;
    }

复杂度

$O(n)$

证明比较繁琐,参见<<算法导论>> ,直观上根据算法可知,只是不断的递归找该索引在的高区或者低区,没有排序,只是做了线性的选择,复杂度应为$O(n)$

0
广告 广告

评论区