专栏首页mathorLeetCode215.数组中的第K个最大元素

LeetCode215.数组中的第K个最大元素

题目链接:LeetCode215

 第一种做法,直接排序完了取,时间复杂度O(logn)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

 第二种做法,BFPRT算法,时间复杂度O(n)

class Solution {
    public static int getMinKthByBFPRT(int[] arr,int k) {
        int[] copyArr = new int[arr.length];
        copyArr = copyArray(arr);
        return bfprt(copyArr,0,copyArr.length - 1,k - 1);
    }
    public static int[] copyArray(int[] arr) {
        int[] tmp = new int[arr.length];    
        for(int i = 0;i != arr.length;i++) 
            tmp[i] = arr[i];
        return tmp;
    }
    public static int bfprt(int[] arr,int begin,int end,int i) {//begin到end范围内求第i小的数
        if(begin == end)
            return arr[begin];
        int pivot = medianOfMedians(arr,begin,end);//中位数作为划分值
        int[] pivotRange = partition(arr,begin,end,pivot);//进行划分,返回等于区域
        if(i >= pivotRange[0] && i <= pivotRange[1]) 
            return arr[i];
        else if(i < pivotRange[0])
            return bfprt(arr,begin,pivotRange[0] - 1,i);
        else 
            return bfprt(arr,pivotRange[1] + 1,end,i);
    }
    
    public static int medianOfMedians(int[] arr,int begin,int end) {
        int num = end - begin + 1;
        int offset = num % 5 == 0 ? 0 : 1;
        int[] mArr = new int[num / 5 + offset];
        for(int i = 0; i < mArr.length;i++) {
            int beginI = begin + i * 5;
            int endI = beginI + 4;
            mArr[i] = getMedian(arr,beginI,Math.min(end,endI));
        }
        return bfprt(mArr,0,mArr.length - 1,mArr.length / 2);
    }
    
    public static int getMedian(int[] arr,int begin,int end) {
        Arrays.sort(arr,begin,end);
        int sum = end + begin;
        int mid = (sum / 2) + (sum % 2);
        return arr[mid];
    }
    
    public static void insertSort(int[] arr,int begin,int end) {
        for(int i = begin + 1;i != end + 1;i++) {
            for(int j = i;j != begin;j--) {
                if(arr[j - 1] > arr[j]) 
                    swap(arr,j - 1,j);
                else 
                    break;
            }
        }
    }
    public static int[] partition(int[] arr,int begin,int end,int pivotValue) {
        int small = begin - 1;
        int cur = begin;
        int big = end + 1;
        while(cur != big) {
            if(arr[cur] < pivotValue)
                swap(arr,++small,cur++);
            else if(arr[cur] > pivotValue)
                swap(arr,cur,--big);
            else 
                cur++;
        }
        int[] range = new int[2];
        range[0] = small + 1;
        range[1] = big - 1;
        return range;
    }
    
    public static void swap(int[] arr,int i,int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    public int findKthLargest(int[] nums, int k) {
        return getMinKthByBFPRT(nums,nums.length - k + 1);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CodeForces D.Powerful array(Div.1)

     大意是是说,问区间[L,R]内的的一个值,这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle,...

    mathor
  • BFPRT算法

     首先将原数组分成5个一组,每组内进行排序,组间不排序,然后将每组的中位数取出再次进行上述操作,直到最后只能分成一组了,然后取出中位数,将这个中位数当作标尺进行...

    mathor
  • 搜索(4)

    mathor
  • ECJTUACM16 Winter vacation training #5 题解&源码

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • loj#6073. 「2017 山东一轮集训 Day5」距离(费用流)

    我们可以把图行列拆开,同时对于行/列拆成很多个联通块,然后考虑每个点所在的行联通块/列联通块的贡献。

    attack
  • CodeForces D.Powerful array(Div.1)

     大意是是说,问区间[L,R]内的的一个值,这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle,...

    mathor
  • 13:大整数的因子

    13:大整数的因子 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 已知正整数k满足2<=k<=9,现给出长度最大为30位...

    attack
  • BFPRT算法

     首先将原数组分成5个一组,每组内进行排序,组间不排序,然后将每组的中位数取出再次进行上述操作,直到最后只能分成一组了,然后取出中位数,将这个中位数当作标尺进行...

    mathor
  • 《linux c 编程一站式学习》课后部分习题解答

    1、假设变量x和n是两个正整数,我们知道x/n这个表达式的结果要取Floor,例如x是17,n是4,则结果是4。如果希望结果取Ceiling应该怎么写表达式呢?...

    s1mba
  • 浙大版《C语言程序设计(第3版)》题目集 习题10-6 递归求Fabonacci数列

    f(n)=f(n−2)+f(n−1) (n≥2),其中f(0)=0,f(1)=1。

    C you again 的博客

扫码关注云+社区

领取腾讯云代金券