- 浏览: 172684 次
- 性别:
- 来自: 济南
文章分类
最新评论
Kth Largest Element in an Array
给定一个无序的数组,找出第K大的元素,假定k一直有效,1 ≤ k ≤ array's length。
例如给定:nuts[] = [3,2,1,5,6,4], k = 2
返回 5
如果我们用Arrays的sort方法将数组排序,然后输出nums[nums.length - k]就是第k大的元素。代码如下:
如果我们在面试中遇到这个问题,这显然不是面试者想考察的地方。我们可以用快排是解决这个问题,在数组中取一个元素作为pivot,第一次循环后,查看pivot的位置,通过它的位置来递归找到第k大的元素。代码如下:
给定一个无序的数组,找出第K大的元素,假定k一直有效,1 ≤ k ≤ array's length。
例如给定:nuts[] = [3,2,1,5,6,4], k = 2
返回 5
如果我们用Arrays的sort方法将数组排序,然后输出nums[nums.length - k]就是第k大的元素。代码如下:
public class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length-k]; } }
如果我们在面试中遇到这个问题,这显然不是面试者想考察的地方。我们可以用快排是解决这个问题,在数组中取一个元素作为pivot,第一次循环后,查看pivot的位置,通过它的位置来递归找到第k大的元素。代码如下:
public class Solution { public int findKthLargest(int[] nums, int k) { return quickSort(0, nums.length - 1, nums, k); } public int quickSort(int l, int r, int[] nums, int k) { int i = l, j = r, pivot = nums[l]; while(i < j) { while(i < j && nums[j] >= pivot) j --; if(i < j) nums[i++] = nums[j]; while(i < j && nums[i] <= pivot) i ++; if(i < j) nums[j--] = nums[i]; } nums[i] = pivot; if(nums.length - i == k) return nums[i]; if(nums.length - i < k) return quickSort(l, i - 1, nums, k); return quickSort(i + 1, r, nums, k); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 221You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 447Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 426Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 550Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 ...
Kth Largest Element in an Array 桶排序 First Missing Positive 计数排序 H-Index 基数排序 Maximum Gap 其他 Largest Number 小结 查找 Search for a Range Search Insert Position Search in Rotated Sorted ...
Array(方法1:堆 方法二:快速排序(推荐)) (面试题40:最小的k个数) LeetCode 347 Top K Frequent Elements(堆排序、桶排序) LintCode 532 Reverse Pairs(归并排序的应用)(面试题51:数组中的逆序对) ...
lru缓存leetcode 力码 大批 152-最大乘积子阵列,169-多数元素,189-...215-Kth Largest element in an Array(Heap Sort), HARD: 218-The Skyline Problem(Mergesort) ) 动态规划 HARD: 174-Dungeon Game, HARD: 188
kth largest element in an array . use heap, use quick select. maximal square. Use dynamic programming. use just O(n) space. The extra space equals matrix col length. majority element ii . 使用 "摩尔...
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
largest element from an unsorted array in linear time. (1) If the number of elements in an array is large .Divide the array into arrays each with 5 elements. n/5 arrays. (2) Compute Median of these 5 ...
in an array 3. Find the "Kth" max and min element of an array 4. Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo 5. Move all the negative elements to ...
in an array *Find the "Kth" max and min element of an array *Given an array which consists of only 0, 1 and 2. Sort the array with *Move all the negative elements to one side of the array *Find the ...
largest element in array 4. Improvements in Java 8 - For HashMap if hashcode collision count is more than 8 in a row , then its internal structure is changed from linked list to tree 渐近分析 big- \...
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ Effective Learning 快速学习法:一年搞定MIT计算机课程 斯考特的FAQ页面 计划 表头 1 2 3 4 运动 健身 刷脂 篮球 羽毛球 游泳、跑步 拳击 学习...