1 用栈实现队列
- 题目链接：232. 用栈实现队列
1.1 题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用
list或者deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例1:
输入: [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出: [null, null, null, 1, 1, false]
解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
进阶：
- 你能否实现每个操作均摊时间复杂度为
O(1)的队列？换句话说，执行n个操作的总时间复杂度为O(n)，即使其中一个操作可能花费较长时间。
1.2 思路
队列的原则是“先入先出”(FIFO)，而栈则相反，是“先入后出”(FILO), 因而通过栈来实现队列，需要实现将栈底元素先进行输出，因此需要建立两个栈，一个负责入队操作，另一个则负责出队操作。入队时直接将元素压入入队栈即可；出队时，将入队栈中的元素全部压入出队栈，然后将栈顶元素弹出，最后将出队栈中的元素重新压入入队栈即可。
但实际上并不需要每次要出队都进行元素的转移，元素入队还是直接压入入队栈即可，而出队时首先判断出队栈是否为空，此时出队栈不为空时实际上就是真实的队列顺序，直接弹出栈顶元素即可；而如果出队栈为空，那么将入队栈中元素压入出队栈再进行弹出即可。
此外，peek()和pop()其实只相差是否将队头元素弹出，因而pop()可以通过调用peek()函数然后弹出队头元素最后返回相应的结果即可。
完整代码如下：
Cpp实现
class MyQueue {
private:
stack<int> stk4In, stk4Out;
void In2Out(){ //实现入队栈中元素到出队栈的转移
while(!stk4In.empty()){
stk4Out.push(stk4In.top()); //将入队栈栈顶压入出队栈
stk4In.pop();
}
}
public:
MyQueue() {}
void push(int x) {
stk4In.push(x); //入队操作，直接将元素压入入队栈
}
bool empty() { //队列为空的条件是两个栈均为空
return stk4In.empty() && stk4Out.empty();
}
int peek() {
if(empty()){
return -1;
}else if(stk4Out.empty()){
In2Out(); //出队栈为空时需要先进行元素转移
}
return stk4Out.top(); //返回出队栈栈顶元素
}
int pop() {
int num = peek(); //获取出队栈栈顶元素
stk4Out.pop(); //将出队栈栈顶元素弹出，即将队头元素出队
return num;
}
};C实现
typedef struct { //定义栈结构体
int *stk; //用数组实现栈
int stk_top; //定义栈顶指针
int capacity; //定义栈的容量
}Stack;
Stack *myStackCreate(int capacity){
Stack *stack = (Stack *)malloc(sizeof(Stack)); //申请栈
stack->stk = (int *)malloc(sizeof(int) * capacity);
stack->stk_top = 0; //初始化栈顶指针
stack->capacity = capacity;
return stack;
}
void StackPush(Stack *obj, int val){ //一般要加上是否栈已满的判断
obj->stk[obj->stk_top++] = val; //入栈操作
}
int StackPeek(Stack *obj){ //获取栈顶元素
if(obj->stk_top == 0) return -1;
return obj->stk[obj->stk_top - 1];
}
void StackPop(Stack *obj, int *ret){
if(obj->stk_top == 0) return;
*ret = obj->stk[--obj->stk_top]; //引用形式，将栈顶元素赋给ret
}
bool isStackEmpty(Stack *obj){
if(obj->stk_top == 0) return true;
return false;
}
void StackFree(Stack *obj){
free(obj->stk);
free(obj);
}
typedef struct {
Stack *inStack; //入队栈
Stack *outStack; //出队栈
} MyQueue;
void in2out(Stack *inStack, Stack *outStack){ //实现两个栈的元素转移
while(!isStackEmpty(inStack)){
int x;
StackPush(outStack, inStack->stk[inStack->stk_top - 1]);
StackPop(inStack, &x);
}
}
MyQueue* myQueueCreate() {
MyQueue *queue = (MyQueue *)malloc(sizeof(MyQueue));
queue->inStack = myStackCreate(100); //创建入队栈
queue->outStack = myStackCreate(100); //创建出队栈
return queue;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(obj->inStack, x); //入队，将元素压入入队栈
}
int myQueuePop(MyQueue* obj) {
int x = 0;
if(!isStackEmpty(obj->outStack)){ //出队栈不为空，直接返回栈顶元素并弹出栈顶
StackPop(obj->outStack, &x);
return x;
}
in2out(obj->inStack, obj->outStack); //出队栈为空，进行元素转移
StackPop(obj->outStack, &x);
return x;
}
int myQueuePeek(MyQueue* obj) {
if(!isStackEmpty(obj->outStack)){
return StackPeek(obj->outStack);
}
in2out(obj->inStack, obj->outStack); //出队栈为空，进行元素转移
return StackPeek(obj->outStack);
}
bool myQueueEmpty(MyQueue* obj) {
return isStackEmpty(obj->inStack) && isStackEmpty(obj->outStack);
}
void myQueueFree(MyQueue* obj) {
StackFree(obj->inStack);
StackFree(obj->outStack);
free(obj);
} 2 用队列实现栈
- 题目链接：225. 用队列实现栈
2.1 题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。
注意：
- 你只能使用队列的基本操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。 你可以使用
list（列表）或者deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例1:
输入: [“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
进阶：你能否仅用一个队列来实现栈。
2.2 思路
栈为“先入后出”(FILO)的数据结构，而队列则是“先入先出”(FIFO),为通过队列来实现栈的操作，可以通过建立两个队列来完成。当元素入栈时，将其压入队列2，然后将队列1中的所有元素出队并压入队列2,这样就可以实现FILO。为了在调用过程中需要判断队列1还是队列2哪个为空来作为入栈的选择，出队时也要先判断哪个队列不为空从而输出该队列的队头。
完整代码如下：
Cpp实现
class MyStack {
private:
queue<int> q1, q2;
void one2two(){ //将队列1元素转移到队列2
while(!q1.empty()){
q2.push(q1.front());
q1.pop();
}
}
void two2one(){ //将队列2元素转移到队列1
while(!q2.empty()){
q1.push(q2.front());
q2.pop();
}
}
public:
MyStack() {}
void push(int x) {
if(q1.empty()){ //此时元素在队列2中，因而这次把队列1作为容器
q1.push(x); //先压入队列1
two2one(); //将队列2元素压入队列1
}else{ //此时元素在队列1中，因而这次把队列2作为容器
q2.push(x);
one2two();
}
}
bool empty() {
return q1.empty()&&q2.empty(); //两个队列均为空则栈为空
}
int top() {
if(empty()) return -1;
else if(q1.empty()) return q2.front(); //判断元素现在在哪个队列，输出对应的队头
return q1.front();
}
int pop() {
int num = top();
if(q1.empty()){
q2.pop();
}else{
q1.pop();
}
return num;
}
};C实现
int front1, rear1, front2, rear2;
typedef struct {
int arr[101];
} MyQueue;
typedef struct {
MyQueue *stack;
MyQueue *tmpQueue;
} MyStack;
MyStack* myStackCreate() {
MyStack *ret = malloc(sizeof(MyStack));
ret->stack = malloc(sizeof(MyQueue));
ret->tmpQueue = malloc(sizeof(MyQueue));
front1 = rear1 = front2 = rear2 = 0;
return ret;
}
void myStackPush(MyStack* obj, int x) {
obj->tmpQueue->arr[rear2++] = x;
while(front1 != rear1){
obj->tmpQueue->arr[rear2++] = obj->stack->arr[front1++];
}
front1 = rear1 = 0;
while(front2 != rear2){
obj->stack->arr[rear1++] = obj->tmpQueue->arr[front2++];
}
front2 = rear2 = 0;
}
int myStackPop(MyStack* obj) {
int x = obj->stack->arr[front1++];
return x;
}
int myStackTop(MyStack* obj) {
int x = obj->stack->arr[front1];
return x;
}
bool myStackEmpty(MyStack* obj) {
return (front1 == rear1);
}
void myStackFree(MyStack* obj) {
free(obj->stack);
free(obj->tmpQueue);
free(obj);
} 3 有效的括号
- 题目链接：20. 有效的括号
3.1 题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例1:
输入: s = “()”
输出: true
示例2:
输入: s = “()[]{}”
输出: true
示例3:
输入: s = “(]”
输出: false
示例4:
输入: s = “([)]”
输出: false
示例5:
输入: s = “{[]}”
输出: true
3.2 思路
创建一个栈，当遇到左括号就将该符号进栈；遇到右括号就检查栈顶元素是否与该符号构成一对符号，若是则继续对字符串进行遍历，否则说明出现不成对的括号，返回false. 完成遍历后，如果栈内还有元素，则说明字符串中有不成对的括号，返回false；若栈为空说明字符串中的括号都一一匹配，返回true。
完整代码如下：
Cpp实现
class Solution {
public:
char getPair(char ch){
if(ch == ')'){
ch = '(';
}else if(ch == ']'){
ch = '[';
}else{
ch = '{';
}
return ch;
}
bool isValid(string s) {
stack<char> stk;
for(char ch:s){
if(ch == '(' || ch == '[' || ch =='{'){
stk.push(ch);
}else{
if(stk.empty() || stk.top() != getPair(ch)){
return false;
}
stk.pop();
}
}
return stk.empty();
}
};C实现
char getPairs(char ch){
if(ch==')') return '(';
else if(ch==']') return '[';
else if(ch=='}') return '{';
return 0;
}
bool isValid(char * s){
int n = strlen(s);
char *stack = malloc(sizeof(char)*n);
int stack_top = 0;
if(n%2!=0) return false;
for(int i=0;i<n;i++){
char ch = getPairs(s[i]);
if(ch){
if(stack_top==0||stack[stack_top-1]!=ch){
return false;
}
stack_top--;
}else{
stack[stack_top++] = s[i];
}
}
return stack_top==0;
} 4 删除字符串中的所有相邻重复项
- 题目链接：1047. 删除字符串中的所有相邻重复项
4.1 题目描述
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例1:
输入: “abbaca”
输出: “ca”
解释:
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
4.2 思路
创建一个栈，遍历字符串，每次先判断当前遍历字符是否与栈顶元素相等，如果相等则可以消掉，即将该元素出栈(题目中只可以对两个相邻的相同字母进行抵消，连续三个相同的字符也只能消两个，其实这里加一个循环即可实现)；如果不同则将该字符进栈。遍历完成后将栈内元素输出到答案字符串中，但由于栈输出的方向与实际方向相反，所以需要对答案字符串进行反转，最后得到最终的答案字符串。
完整代码如下：
Cpp实现
class Solution {
public:
void reverse(string& s){
int l = 0, r = s.length()-1;
while(l < r){
char ch = s[l];
s[l++] = s[r];
s[r--] = ch;
}
}
string removeDuplicates(string s) {
stack<char> stk;
for(char ch: s){
if(!stk.empty() && ch == stk.top()){
stk.pop();
}else{
stk.push(ch);
}
}
string res = "";
while(!stk.empty()){
res += stk.top();
stk.pop();
}
reverse(res);
return res;
}
};C实现
void stringReversal(char *str, int strSize){
for(int l = 0, r = strSize - 1; l<=r; l++,r--){
char tmp = str[l];
str[l] = str[r];
str[r] = tmp;
}
}
char * removeDuplicates(char * s){
if(strlen(s) <= 1) return s;
char *stk = (int *)malloc(sizeof(char) * strlen(s));
int stk_top = 0;
for(int i = 0; i < strlen(s); i++){
if(stk_top == 0 || stk[stk_top - 1] != s[i]){
stk[stk_top++] = s[i];
}else{
stk_top--;
}
}
int index = 0;
while(stk_top != 0){
s[index++] = stk[--stk_top];
}
stringReversal(s, index);
s[index] = '\0';
return s;
} 5 逆波兰表达式求值
- 题目链接：150. 逆波兰表达式求值
5.1 题目描述
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例1:
输入: tokens = [“2”,”1”,”+”,”3”,”“]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9
示例2:
输入: tokens = [“4”,”13”,”5”,”/“,”+”]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例3:
输入: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”“,”/“,”“,”17”,”+”,”5”,”+”]
输出: 22
解释: 该算式转化为常见的中缀算术表达式为：
((10 (6 / ((9 + 3) -11))) + 17) + 5
= ((10 (6 / (12 -11))) + 17) + 5
= ((10 (6 / -132)) + 17) + 5
= ((10 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
5.2 思路
创建一个栈，将遍历整个tokens, 遇到数字就进栈，遇到符号就将栈顶两个元素取出进行相应的运算，然后将运算结果入栈 ，直到整个tokens遍历完成。应该注意，tokens[i]的第一位出现-号可能是数字，也可能是运算符，需要进行判断，最简单的就是判断其长度，为1说明就是运算符。其次，还要注意 运算的顺序 ，栈顶元素为运算符后的数字，而栈顶第二个元素是运算符前的数字。
完整代码如下：
Cpp实现
class Solution {
public:
int getNum(string str){
bool flag = false;
int ptr = 0;
if(str[0] == '-'){
flag = true;
++ptr;
}
int res = 0;
for(; ptr < str.length(); ++ptr){
res *= 10;
res += str[ptr] - '0';
}
return flag ? -res : res;
}
int cal(int num1, int num2, char token){
if(token == '+'){
return num1+num2;
}else if(token == '-'){
return num1-num2;
}
else if(token == '*'){
return num1*num2;
}
return num1 / num2;
}
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for(string str: tokens){
if(str.length() == 1 && (str[0] < '0' || str[0] > '9')){
int num2 = stk.top(), num1;
stk.pop();
num1 = stk.top();
stk.pop();
stk.push(cal(num1, num2, str[0]));
}else{
stk.push(getNum(str));
}
}
return stk.top();
}
};C实现
bool isNegative(char *str){
if(str[0] == '-' && str[1]!='\0') return true;
return false;
}
bool isNum(char *str){
if(isNegative(str)) return true;
if(str[0] != '-' && str[0] != '+' && str[0]!='*' && str[0] != '/') return true;
return false;
}
int getNum(char *str){
int index = 0, num = 0;
bool Negative = isNegative(str);
if(Negative){
index++;
}
while(str[index] != '\0'){
num *= 10;
num += (str[index++] - '0');
}
return Negative ? -num : num;
}
void cal(char *str, int left, int right, int *ret){
if(str[0] == '+'){
*ret = left + right;
}else if(str[0] == '-'){
*ret = left - right;
}else if(str[0] == '*'){
*ret = left * right;
}else{
*ret = left / right;
}
}
int evalRPN(char ** tokens, int tokensSize){
int stack[5001], stk_top = 0;
for(int i = 0; i < tokensSize; i++){
if(isNum(tokens[i])){
stack[stk_top++] = getNum(tokens[i]);
continue;
}
int right = stack[--stk_top];
//return stk_top;
int left = stack[--stk_top];
cal(tokens[i], left, right, stack+stk_top);
stk_top++;
}
return stack[0];
} 6 滑动窗口最大值
- 题目链接：239. 滑动窗口最大值
6.1 题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例1:
输入: nums = [1,3,-1,-3,5,3,6,7], k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
-——————— ——-
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例2:
输入: nums = [1], k = 1
输出: [1]
6.2 思路
题目要求每个滑动窗口的最大值，那么就希望能够用一个数组去存放窗口滑动过程中的最大值，但是有一个问题，当目前的最大值不在窗口内需要将其弹出，然后最大值就变成原本数组中的次大值或者当前窗口的最后一个数字。
基于上边的思路，可以采用双端单调队列，队头为当前最大值，沿正向方向呈递减趋势。遍历数组，当当前数字大于队尾元素时将队尾元素弹出，否则将当前数字插入队尾，从而保证队列为单调队列，然后每次移动窗口时只需要将队头元素对应的数字插入答案即可。注意，每次移动窗口需要判断队头元素在不在窗口内，如果不在需要先将队头弹出。
完整代码如下：
Cpp实现
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> deq; //创建双端队列
int n = nums.size();
vector<int> res;
for(int i = 0; i < n; ++i){
if(!deq.empty() && i==deq.front()+k){
deq.pop_front(); //如果队头不在窗口内，则弹出
}
while(!deq.empty() && nums[deq.back()] < nums[i]){
deq.pop_back(); //如果队尾元素小于窗口最右侧数值，则将队尾弹出
}
deq.push_back(i); //将窗口最右端元素插入队尾
if(i >= k-1){ //此时才到达窗口最右端，进行答案插入
res.emplace_back(nums[deq.front()]);
}
}
return res;
}
};注意：上述代码中是从数组开头遍历，需要遍历到第一个窗口的最右端时才开始将队头元素插入到答案中。
C实现
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
int queue[numsSize];
int front = 0, rear = 0;
int* ret = malloc(sizeof(int) * (numsSize - k + 1));
*returnSize = numsSize - k + 1;
for(int i = 0; i < k; i++){
while(rear!=front && nums[i] >= nums[queue[rear-1]]) rear--;
queue[rear++] = i;
}
for(int i = 0; i < (numsSize-k); i++){
ret[i] = nums[queue[front]];
while(rear!=front && nums[i+k] >= nums[queue[rear-1]]) rear--;
queue[rear++] = i+k;
if(i == queue[front]) front++;
}
ret[numsSize-k] = nums[queue[front]];
return ret;
} 7 前 K 个高频元素
- 题目链接：347. 前 K 个高频元素
7.1 题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例2:
输入: nums = [1], k = 1
输出: [1]
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
7.2 思路
哈希+sort：遍历整个数组，以元素值为键插入哈希表中，如果当前元素在哈希表中已经存在，则该键对应的值加1. 然后对哈希表按值进行排序，最后直接输出值前k大所对应的键即可. 这种做法时间复杂度为O(nlogn)。(C实现)
哈希+堆排序：同样用哈希来统计字符出现频率，然后通过堆按频率进行排序，堆容量为k，遍历完成后直接将堆内元素按顺序输出即可。STL标准库中可用优先队列priority_queue来实现。(cpp实现)
哈希+sort：遍历整个数组，以元素值为键插入哈希表中，如果当前元素在哈希表中已经存在，则该键对应的值加1. 然后对哈希表按值进行排序，最后直接输出值前k大所对应的键即可. 这种做法时间复杂度为O(nlogn)。(C实现)
哈希+堆排序：同样用哈希来统计字符出现频率，然后通过堆按频率进行排序，堆容量为k，遍历完成后直接将堆内元素按顺序输出即可。STL标准库中可用优先队列priority_queue来实现。(cpp实现)
完整代码如下：
Cpp实现
struct node{
int cnt;
int num;
node(int num_, int cnt_): num(num_), cnt(cnt_){};
friend bool operator < (node a, node b){
return a.cnt > b.cnt;
}
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m;
for(int i: nums) m[i]++;
priority_queue<node> pq;
for(auto &[num, cnt]: m) {
if(pq.size() == k) {
if(cnt < pq.top().cnt) continue;
pq.pop();
}
pq.push(node(num, cnt));
}
vector<int> ret;
while(!pq.empty()) {
ret.emplace_back((pq.top()).num);
pq.pop();
}
return ret;
}
};三刷tips：当数据类型为用户自定义，如pair，那么需要对优先队列中的比较函数进行重载，但需要注意，不能简单写个
cmp函数进行调用，而是需要用一个结构体或者类去封装，然后将优先队列的数据类型指定为这个结构体/类，然后在结构体或类中重载比较算子。重载operator<需要用friend关键字修饰。
C实现
typedef struct {
int val;
int key;
UT_hash_handle hh;
}HashMap;
bool cmp(const void *a, const void *b){
return (((HashMap *)a)->val < ((HashMap *)b)->val); //从大到小
}
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
HashMap *map = NULL, *tmp;
for(int i = 0; i < numsSize; ++i){
HASH_FIND_INT(map, nums+i, tmp);
if(tmp){
tmp->val++;
}else{
tmp = (HashMap*)malloc(sizeof(HashMap));
tmp->key = nums[i];
tmp->val = 1;
HASH_ADD_INT(map, key, tmp);
}
}
HASH_SORT(map, cmp);
int* ret = (int *)malloc(sizeof(int)*k);
*returnSize = 0;
HashMap *s;
HASH_ITER(hh, map, s, tmp){
if(*returnSize < k){
ret[(*returnSize)++] = s->key;
}
HASH_DEL(map, s);
}
return ret;
} 总结
404…
