Leetcode 41. 缺失的第一个正数
题目描述
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 10^5
-2 ^31 <= nums[i] <= 2 ^31 - 1
C语言题解和思路
int firstMissingPositive(int* nums, int numsSize) {
int *table = (int *)malloc(sizeof(int) * (numsSize + 1));
memset(table, 0, sizeof(int) * (numsSize + 1));
int i;
for(i = 0; i < numsSize; i++)
{
if(nums[i] <= numsSize && nums[i] > 0)
{
table[nums[i]]++;
}
}
for(i = 1; i < numsSize + 1; i++)
{
if(table[i] == 0)
{
return i;
}
}
return numsSize + 1;
}
解题思路
哈希表
建立一个比数组长度大一位的数组 table 作为哈希表，并将它初始化为 0 。
循环遍历数组 nums ，如果该位置的值大于 0 并且不小于数组长度，让哈希表 table 在该值的位置自加。
从下标 1 开始循环遍历哈希表，如果在某个下标哈希表的值为 0 ，直接返回这个下标。
如果循环结束没有返回任何值，则返回数组长度加一。
Leetcode 155. 最小栈
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例 1：
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
- -2 ^31 <= val <= 2 ^31 - 1
- pop、top 和 getMin 操作总是在 非空栈 上调用
- push, pop, top, and getMin最多被调用 3 * 10^4 次
C语言题解和思路
typedef struct MinStack{
int data[10000];
int top;
int min[10000];
int mintop;
} MinStack;
MinStack* minStackCreate() {
MinStack *head = (MinStack *)malloc(sizeof(MinStack));
head->top = 0;
head->mintop = 0;
return head;
}
void minStackPush(MinStack* obj, int val) {
if(obj->mintop == 0 || val <= obj->min[obj->mintop - 1])
{
obj->min[obj->mintop++] = val;
}
obj->data[obj->top++] = val;
}
void minStackPop(MinStack* obj) {
if( obj->min[obj->mintop - 1] == obj->data[obj->top - 1])
{
obj->mintop--;
}
obj->top--;
}
int minStackTop(MinStack* obj) {
return obj->data[obj->top - 1];
}
int minStackGetMin(MinStack* obj) {
return obj->min[obj->mintop - 1];
}
void minStackFree(MinStack* obj) {
free(obj);
}
/**
* Your MinStack struct will be instantiated and called as such:
* MinStack* obj = minStackCreate();
* minStackPush(obj, val);
* minStackPop(obj);
* int param_3 = minStackTop(obj);
* int param_4 = minStackGetMin(obj);
* minStackFree(obj);
*/
解题思路
定义一个结构体，数组 data 用于存放推进的数据，数组 min 用于存放最小值，变量 top 存放最后进入的数在 data 的下标，变量 mintop 记录最小值在 min 中的下标。
初始化栈时，将 mintop 和 top 初始化为 0 ，返回定义好的指针。
将数据推入栈时：
- 如果栈中没有最小值或该数小于栈中的最小值时，将该值存入数组 min 中，并更新 mintop 。
- 将该数据存入数组 data 中，并更新 top 。
将栈顶数据退出栈时：
- 如果需要推出栈的值等于栈中的最小值，将 mintop 前移一位，将 min 的最小值推出。
- 将 top 前移一位，将 data 最后进入的值推出。
返回栈顶元素时，根据 top 的值返回数组 data 中的元素。
获取堆栈中的最小元素时，根据 mintop 的值返回数组 miin 中的元素。
