题目：
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例：
输入：[3,? 30,? 34,? 5,? 9]
输出："
3033459"
解题思路：?
求拼接数的大小问题可以转化成字符串的拼接问题。
拼接字符串：
1. x + y > y + x 可得：x 大于 y
2.?x + y <?y + x 可得：x 小于 y
例如：x =? "12" , y = "30" ,? ?"1230" < "3012"所以"12"排在"30"的前面。
C++代码：
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> str;
for(int i = 0; i < nums.size(); i++)
{
//to_string 将整数转化为字符串
str.push_back(to_string(nums[i]));
}
quick_sort(str, 0, str.size()-1);
string res;
for(auto item: str)
res.append(item);
return res;
}
private:
void quick_sort(vector<string> &str, int l, int r){
if(l >= r) return ;
int i = l - 1, j = r + 1;
//正确
string x = str[(l+r)/2];
while(i < j)
{
do j--; while(str[j] + x > x + str[j]);
do i++; while(str[i] + x < x + str[i]);
if(i < j) swap(str[i], str[j]);
}
quick_sort(str, l, j);
quick_sort(str, j+1, r);
}
};题目：
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例：
输入：[1, 2, 3, 4, 5]
输出：True
解题思路：?
将抽出来的五张牌进行排序,? 循环遍历判读nums[i] = nums[i + 1] 是否成立进行判重。
C++代码：
class Solution {
public:
bool isStraight(vector<int>& nums) {
sort(nums.begin(), nums.end());
//存储大小王的个数
int temp = 0;
for(int i = 0; i < 4; i++)
{
if(nums[i] == 0)
temp++;
else if(nums[i] == nums[i+1])
return false;
}
return nums[4] - nums[temp] < 5;
}
};题目：
输入整数数组?arr?，找出其中最小的?k?个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例：
输入：arr = [3, 2, 1], k = 2
输出：[1, 2] 或者 [2, 1]
解题思路：?
快排+遍历
快排模板：
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}C++代码：
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
quicksort(arr, 0, arr.size()-1);
vector<int> res;
for(int i = 0; i < k; i++)
{
res.push_back(arr[i]);
}
return res;
}
private:
void quicksort(vector<int> &arr, int l, int r){
if(l >= r) return ;
int i = l - 1, j = r + 1;
int x = arr[(l + r) / 2];
while(i < j)
{
do i++; while(arr[i] < x);
do j--; while(arr[j] > x);
if(i < j) swap(arr[i], arr[j]);
}
quicksort(arr, l, j);
quicksort(arr, j+1, r);
}
};题目：
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4]?的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
示例：
输入：
["MedianFinder",? "addNum",? ?"addNum",? "findMedian",? "addNum",? "findMedian"]
[[],? [1],? [2],? [],? [3],? []]输出：[null,? null,? null,? 1.50000,? null,? 2.00000]
解释：
MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
解题思路：?
建立小顶堆 A 和大顶堆 B，其中 B 放较小的一半数、A 放较大的一半数
????????如果 A.size() == B.size() ，则中位数为(A?的堆顶元素 +?B?的堆顶元素) / 2；
????????如果 A.size() != B.size()，则中位数为A 的堆顶元素
小堆顶的建立：
priority_queue<int,? vector<int>,? greater<int>> A;
大堆顶的建立：
priority_queue<int,? vector<int>,? less<int>> B;
C++代码：
class MedianFinder {
public:
/** initialize your data structure here. */
//升序队列, 小顶堆, 存储较大的一部分
priority_queue<int, vector<int>, greater<int>> A;
//降序队列, 大顶堆, 存储较小的一部分
priority_queue<int, vector<int>, less<int>> B;
MedianFinder() {
}
//从数据流中添加一个整数到数据结构中
void addNum(int num) {
if(A.size() == B.size())
{
B.push(num);
A.push(B.top());
B.pop();
}
else
{
A.push(num);
B.push(A.top());
A.pop();
}
}
//返回目前所有元素的中位数
double findMedian() {
if(A.size() != B.size()) return A.top();
else return (A.top() + B.top())/2.0;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/