215. Kth Largest Element in an Array

Posted on | In
Words count in article: 242 | Reading time ≈ 1

题目

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

示例1:

1
2
Input: [3,2,1,5,6,4] and k = 2
Output: 5

示例2：

1
2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

提示:

  1. You may assume k is always valid, 1 ≤ k ≤ array’s length.

解法

解法一：

排序，直接返回nums[nums.length - k]

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Node {
		private char c;
		private int times;
		
		public Node(char c, int times) {
			this.c = c;
			this.times = times;
		}

		public char getC() {
			return c;
		}

		public void setC(char c) {
			this.c = c;
		}

		public int getTimes() {
			return times;
		}

		public void setTimes(int times) {
			this.times = times;
		}
	}
	 public String frequencySort(String s) {
		 int[] chars = new int[256];
		 for (char c : s.toCharArray()) {
			 chars[c]++;
		 }
		 
		 PriorityQueue<Node> charNodes = new PriorityQueue<>((a, b) -> b.getTimes() - a.getTimes());
		 for (int i = 0;i < 256;i++) {
			 if (chars[i] == 0) {
				 continue;
			 }
			 
			 Node node = new Node((char) i, chars[i]);
			 charNodes.add(node);
		 }
		 
		 StringBuilder sb = new StringBuilder();
		 while (!charNodes.isEmpty()) {
			 Node node = charNodes.poll();
			 int total = node.getTimes();
			 while (total > 0) {
				 sb.append(node.getC());
				 total--;
			 }
		 }
		 return sb.toString();
	 }
0%