[TOC]
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
class Solution {
public String minNumber(int[] nums) {
int n = nums.length;
String[] strs = new String[n];
int index = 0;
for (int num : nums) {
strs[index++] = String.valueOf(num);
}
fastSort(strs, 0, n - 1);
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str);
}
return sb.toString();
}
private void fastSort(String[] strs, int low, int high) {
if (low >= high) {
return;
}
int i = low, j = high;
String tmp = strs[i];
while (i < j) {
while ((strs[j] + strs[low]).compareTo(strs[low] + strs[j]) >= 0 && i < j) {
j--;
}
while ((strs[i] + strs[low]).compareTo(strs[low] + strs[i]) <= 0 && i < j) {
i++;
}
tmp = strs[i];
strs[i] = strs[j];
strs[j] = tmp;
}
strs[i] = strs[low];
strs[low] = tmp;
fastSort(strs, low, j - 1);
fastSort(strs, j + 1, high);
}
}class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
StringBuilder res = new StringBuilder();
for(String s : strs) {
res.append(s);
}
return res.toString();
}
}在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
维持一个包含k个元素的小顶堆，遍历一遍nums,取出堆顶即可。
class Solution {
public int findKthLargest(int[] nums, int k) {
Queue<Integer> minQueue = new PriorityQueue<>();
for (int num : nums) {
minQueue.offer(num);
if (minQueue.size() > k) {
minQueue.poll();
}
}
return minQueue.peek();
}
}利用(从小到大)快排的partition操作把数组两边划分成左边小于等于v, 右边大于等于v。(v为基准值)，位置记为p。 若右边的元素比不少于k个，说明第k大的元素在数组的右边， 否则第k大的元素在数组的左边。 注意： 若右边的元素比少于k个，设右边元素个数为lenR，因为右边边已经有lenR个数比现有的位置大了，所以在在数组左边找 第k - lenR大的数。
该递归函数不消耗空间，因为并不需要保存变量。每次平均把数组砍一半，要不递归左边，或者递归右边。
class Solution {
public:
int partition(vector<int>& nums, int l, int r)
{
int x = nums[l+r >> 1];
int i = l - 1, j = r + 1;
while(i < j)
{
do ++i; while(nums[i] < x);
do --j; while(nums[j] > x);
if(i < j)
swap(nums[i], nums[j]);
}
return j;
}
int find_num(vector<int>& nums, int l, int r, int k)
{
if(l >= r) return nums[r];
int p = partition(nums, l, r);
return (r - p) >= k ? find_num(nums, p + 1, r, k) : find_num(nums, 0, p, k-(r - p));
}
int findKthLargest(vector<int>& nums, int k) {
return find_num(nums, 0, nums.size() - 1, k);
}
};平均 时间：O(n) & 空间：O(1) || 最坏：时间：O(n^2) 空间 O(1)
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
最多会对 addNum、findMedia进行 50000 次调用。
class MedianFinder {
Queue<Integer> q1, q2;
/** initialize your data structure here. */
public MedianFinder() {
q1 = new PriorityQueue<>(); // 小顶堆，保存较大的一半
q2 = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
}
public void addNum(int num) {
if (q1.size() != q2.size()) { // 数据流为奇数，先将num插入q1, 然后取q1里面最小的数，放入q2
q1.add(num);
q2.add(q1.poll());
} else {
q2.add(num);
q1.add(q2.poll());
}
}
public double findMedian() {
return q1.size() != q2.size() ? q1.peek() : (q1.peek() + q2.peek()) / 2.0;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:
输入: nums = [1], k = 1 输出: [1] 说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
统计nums中每个元素的次数,，存入hashmap，然后维护一个的大顶堆
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int[] res = new int[k];
Queue<Pair<Integer, Integer>> maxHeap = new PriorityQueue<Pair<Integer, Integer>>((Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) -> {
if (p1.getValue() < p2.getValue()) {
return 1;
} else if (p1.getValue().equals(p2.getValue())){
return 0;
} else {
return -1;
}
});
for (Integer value : map.keySet()) {
maxHeap.offer(new Pair<>(value, map.get(value)));
}
for (int i = 0; i < k; i++) {
res[i] = maxHeap.poll().getKey();
}
return res;
}
}给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入: "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。 示例 2:
输入: "cccaaa"
输出: "cccaaa"
解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。 示例 3:
输入: "Aabb"
输出: "bbAa"
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意'A'和'a'被认为是两种不同的字符。
记录每个字符出现的次数, 然后维护一个大顶堆，每次取出堆顶出去就好了。
class Solution {
public String frequencySort(String s) {
int n = s.length();
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
map.put(c, map.getOrDefault(c, 0) + 1);
}
Queue<Pair<Character, Integer>> maxHeap = new PriorityQueue<Pair<Character, Integer>>((x, y) -> {
if (x.getValue() < y.getValue()) {
return 1;
} else if (x.getValue().equals(y.getValue())) {
return 0;
} else {
return -1;
}
});
for (Character value : map.keySet()) {
maxHeap.offer(new Pair<Character, Integer>(value, map.get(value)));
}
StringBuilder sb = new StringBuilder();
while (!maxHeap.isEmpty()) {
Pair<Character, Integer> pair = maxHeap.poll();
int value = pair.getValue();
while (value-- > 0) {
sb.append(pair.getKey());
}
}
return sb.toString();
}
}