215. Kth Largest Element in an Array

The first solution, the easiest one, time complexity: O(nlog(n))

    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        if(k<=nums.length)
            return nums[nums.length-k];
        else
            return -1;
    }

The second solution, using priority queue, time complexity: O(n*klog(k))

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i:nums){
            q.offer(i);
            if(q.size()>k)
                q.poll();
        }
        return q.peek();
    }

The third soltuion, quick sort the nums, and then return the kth largest num, average time complexity: O(n), the following is a typical quick sort template:

    public int findKthLargest(int[] nums, int k) {
        quicksort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    public void quicksort(int[] nums, int start, int end) {
        if (start >= end)
            return;
        int i = start, j = end, mid = (i + j) / 2;
        int midNum = nums[mid];
        while (i <= j) {
            while (i <= j && nums[i] < midNum) {
                i++;
            }
            while (i <= j && nums[j] > midNum) {
                j--;
            }
            if (i <= j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
        quicksort(nums, start, j);
        quicksort(nums, i, end);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

 

推荐这些技术文章:

leetcode 215. Kth Largest Element in an Array 数组中的第K个最大元素

一、题目大意
https://leetcode.cn/problems/kth-largest-element-in-an-array
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。** **
示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 ...

1060. Missing Element in Sorted Array

My solution:

class Solution {
public int missingElement(int[] nums, int k) {
int i=1;
for(;i<nums.length;i++){
int diff = nums[i]-nums[i-1]-1;
if(diff...

34. Find First and Last Position of Element in Sorted Array

My binary search solution:

class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums==null || nums.length==0)
return new int[]{-1,-1};

int ...

896. Monotonic Array

My solution:

class Solution {
public boolean isMonotonic(int[] nums) {
if(nums==null||nums.length<3){
return true;
}
int first = nums[0];
int secon...

[leetcode] 34. Find First and Last Position of Element in Sorted Array

题目
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write ...

LeetCode 912. Sort an Array

原题链接在这里:https://leetcode.com/problems/sort-an-array/
题目:
Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:
Inpu...

剑指 Offer 03. 数组中重复的数字

class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);

for(int i=0;i<nums.length-1;i++){
if(nums[i]==nums[i+1]){
return num...

747. 至少是其他数字两倍的最大数

class Solution {
public int dominantIndex(int[] nums) {
if(nums.length==1) return 0;
int[] nums1 = new int[nums.length];
for(int i=0;i<nums.length;i++){
nu...

2019-2020 XX Open Cup, Grand Prix of Korea

2019-2020 XX Open Cup, Grand Prix of Korea
比赛收获
本场贡献:et3_tsy :G提供了思路,过了H,H爆了int,贡献WA一发,J有想法,调了1hr后,发现在特例情况复杂度退化,假了
​ 1427314831a:过了A
​ Ryker0923 :过了G,提供了A的思路
一共三道题
总结:本场暴露两个问题:
1)后期乏力
前两个小时过了...

UVA1589 象棋 Xiangqi

这题考察我们的大脑体力,非常难调,我花了2小时,要是在区域赛里做着题,我碰都不碰,没有大样例非常难受。
分析如下:

中国象棋,见百度百科
就是考虑当前情况下将军是不是已经给将死了

考虑:

飞将
将军吃掉了红色棋子的情况
马脚问题
将军只能在一定的区域内移动
注意边界情况
善用工具来debug,我用了udebug,里面有一个大样例,cmd我是可以看到输入的,但吞了我一部分输出,搞得我虚空调试...

文章标题:215. Kth Largest Element in an Array
文章链接:https://www.dianjilingqu.com/51046.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>