给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
题解：数组arr长度为len，要找到最小正整数x，x 肯定在[1, len + 1]之间，因为是正整数，所以肯定大于1，假设 x > len + 1, 那么arr中肯定有 [1, 2, 3, ...., len + 1] 共len + 1个正整数，arr长度为len，矛盾，所以x肯定<=len + 1。
具体算法: 定一个flags数组，数组长度为len + 1， 遍历arr，记录出现在[1, len + 1]的数，并标记在flags中。arr遍历完后，遍历flags，找到第一个没有被标记的正整数x。
时间复杂度 O(n), 空间复杂度 O(n),
```javascript
var firstMissingPositive = function(nums) {
const flags = Array.from({ length: nums.length + 1 }).fill(false);
for (let i = 0; i < nums.length; i++) {
if ((nums[i] > 0) & (nums[i] <= flags.length)) {
flags[nums[i]] = true;
}
}
for (let j = 1; j < flags.length; j++) {
if (flags[j] === false) {
return j;
}
}
return nums.length + 1;
};
```
因为要求空间复杂度为 O(1), 优化下flags，不要求保持原来数组，直接修改原数组即可。
优化后的算法，
最简单的想法是看到[1, len + 1]区间内的数val，下标为idx，就将nums[val] 标为 true，然后将nums[val]原先的那个数放到idx的这个位置，循环处理，等一圈遍历完，看下哪个位置的数组不是true，则是我们想要找到的最小正数
```javascript
var firstMissingPositive = function(nums) {
nums.push(nums.length + 1); // 推入一个哨兵
const { length } = nums;
for (let i = 0; i < length; i++) {
while (
nums[i] > 0 &&
nums[i] < length &&
nums[i] !== true &&
nums[nums[i]] !== true
) {
let value = nums[nums[i]];
if (nums[i] === value) {
nums[nums[i]] = true;
} else {
nums[nums[i]] = true;
nums[i] = value;
if (value === i) {
nums[i] = true;
}
}
}
}
return length;
};
```
代码见上，理论上的时间是O(n),空间是O(1),但是实际上跑起来性能惨不忍睹，估计太多判断以及number和boolean比较导致。再优化优化，我们把nums[val] 置为true的目的是为了找到区间[1, len + 1]某个数，恰好原数组下标是 [0, len), 我们只要把找到的数放到相应的下标即可，判断的时候，看看数和下标是否匹配，不匹配的第一个数就是我们想要的
代码见下，时间复杂度O(n),空间O(1)没变
```javascript
var firstMissingPositive = function(nums) {
nums.push(nums.length + 1); // 推入一个哨兵
const { length } = nums;
for (let i = 0; i < length; i++) {
while (nums[i] > 0 && nums[i] < length && nums[nums[i]] !== nums[i]) {
swap(nums, nums[i], i);
}
}
for (let j = 1; j < length; j++) {
if (nums[j] !== j) {
return j;
}
}
return length;
};
// 交换两个数，用异或或者加减都可以
function swap(nums, x, y) {
let a = nums[x];
nums[x] = nums[y];
nums[y] = a;
}
```
请设计一个抽皮肤算法， 如果玩家往游戏里面充钱越多，则抽中的概率就越大。充钱相同则具有相同的概率。> 注意，游戏玩家数目是动态变化的扩展：- 贵族玩家增加更高的权重w1，即如果之前的概率是p，那么加上贵族之后就是min(1, p * (1 + w1))。比如p是0.5，w1是0.1，那么充了贵族就是min(1, 0.5 * 1.1) = 0.55- 抽…
LeetCode题解 最后剩下谁？1〜50号运动员按顺序排成一排。教练下令：“单数运动员出列！”剰下的运动员重新排队编号。教练又下令：“单数运动员出列！ ”如此下去，最后只剰下一个人，他是几号运动员？如果教练下的令是“双数运动员出列！”最后剰下的又是谁？题解：## 思路如果是双数出列，那么由于1号从来都没有动过，因此剩下的是1号。如果是单数数列，每次剩下的人的编号分别是$2^N$,其中N为轮…
LeetCode题解 链表的冒泡排序可以使用 https://leetcode-cn.com/problems/sort-list/ 进行测试。 但是本题的要求不是时间复杂度$O(N*logN)$，而是要求使用冒泡排序算法题解：## Python Solution```pythonclass Solution: def sortList(self, head: ListNode) -> …
LeetCode题解645. 错误的集合集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。示例 1:输入: nums = [1,2,2,4]输出: [2,…
LeetCode题解计算机为什么是基于二进制的？可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制