【LeetCode 41. 缺失的第一个正数】

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 

示例 1：
输入：nums = [1,2,0]
输出：3

示例 2：
输入：nums = [3,4,-1,1]
输出：2

示例 3：
输入：nums = [7,8,9,11,12]
输出：1

思路：

时间复杂度为O(n)，说明不能嵌套循环。

已知num.size()（后续描述简称len），一共有len个坑，每个坑按顺序与 1 到 len 对应。没有出现的最小的正整数最大的情况是，前面每个坑都填满，此时 res 为 len + 1 ；其余情况下，前 len 个坑中，首个未被填的坑就是当前数组里没有出现的最小的正整数。

也就是说经过调整之后，期望的数组形式应该是，保证数值在 1 到 len 之间的数都落在对应的下标上（因为数组下标是从 0 开始的，所以坐标加一才能与存放的数值相比较）。符合期望的位置上会出现该出现的数值，不符合期望的位置上会存放 -1。

此时，考虑一个边界值，先在容器末尾增加一个位置，赋值 -1 （对应前述的最大情况）。

int n = nums.size();
nums.push_back(-1);

那么，数值不在 1 到 len 之间的数就不需要考虑了。接下来，遍历数组，将存放数值在非期望范围的位置上全部存放 -1。

        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) nums[i] = -1;
        }

接下来，要考虑的是怎么让每个存在期望数值的位置上存放对应的数值呢？

分析一下满足交换数值的条件：

1）发起交换的位置上有符合条件的数值（即 != -1）

2）发起交换的位置上存放着不匹配的数值

3）同意交换的位置上也存放着不匹配的数值

接下来，还需要考虑，发起交换的位置得到的数值仍不匹配怎么办？

循环上述判断，将新获得的不匹配数值交换到匹配的位置上，直到不再满足上述三个条件。

            while (nums[j] != -1 && j + 1 != nums[j] && nums[j] != nums[nums[j] - 1])
                swap(nums[j] , nums[nums[j] - 1]);

每次结束该发起位置的while循环后，如果该发起位置上的数值仍不匹配（例如数组中有重复数值），该位置存放 -1。

if (nums[j] != -1 && j + 1 != nums[j]) nums[j] = -1;

总的 for 循环如下：

        for (int j = 0; j < n ; j++) {
            while (nums[j] != -1 && j + 1 != nums[j] && nums[j] != nums[nums[j] - 1])
                swap(nums[j] , nums[nums[j] - 1]);
            if (nums[j] != -1 && j + 1 != nums[j]) nums[j] = -1;
        }

经过上述两大步处理，得到了期望中的数组，此时只需要找到一个存放 -1 的位置，下标加一返回即可。

        int res;
        for (res = 0; res < n + 1; res++) {
            if (nums[res] == -1) {
                res ++;
                break;
            }
        }
        return res;

提交总览

【LeetCode 128. 最长连续序列】

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

这题有两个思路，一个利用哈希表，一个利用并查集。

先来看哈希表。

首先申请一个无序的哈希表。

unordered_map<int , int> mp;

接下来，遍历nums，对每个出现的数值，在 mp 的对应下标位置上计数为 1 。

for (auto x : nums) mp[x] = 1;

对于每个连续序列的开始，它的前一位不存在（即 计数为 0 ）。当连续序列开始向后探索时，遇到不存在立刻停止，长度为 停止时下标 与 开始时下标 之差。每次结束探索后，与当前存放的最长长度比较，留下更大值。

for (auto x : nums) {
            if (!mp.count(x-1)) {
                int y = x;
                while (mp.count(y)) {
                    y++;
                }
                res = max(res , y-x);
            }
        }

返回 res;

return res;

再来看并查集的解法；

并查集的思路是，先把每个数值都当作一个节点，当遇到相邻后继数值，合并树。每次探索记录节点数（即 连续序列的长度），与当前存放的最大长度比较，留下更大值。

主函数逻辑比较简单：

unordered_map<int, int> fa, cnt;

申请两个无序哈希表，一个存放父节点，一个存放节点数。

    int longestConsecutive(vector<int>& nums) {
        if (!nums.size()) return 0;
        for (auto x : nums) {
            fa[x] = x;
            cnt[x] = 1;
        }
        int res = 1;
        for (auto x : nums) {
            if (fa.count(x+1)) {
                res = max(res, merge(x, x+1));
            }
        }
        return res;
    }

有两个自己编写的工具函数：

find() 和 merge( , )

先来看find函数：

用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}

这里是概念介绍里的写法，有助于理解。但是本题需要更新父节点表的值，所以多了一步赋值。

int find(int x) {
        return x==fa[x] ? x : fa[x]=find(fa[x]);
    }

接下来看 merge 函数：

第一步，使用 find 函数找到 两个对应的根节点。

第二步，将后面的根节点的父节点设置为前面的根节点（结合本题，后面的数值要比前面的大，应该连接在后面）。

第三步，合并后，前面的存放的节点数要加上后面的节点数。

int merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return cnt[x];
        fa[y] = x;
        cnt[x] += cnt[y];
        return cnt[x];
    }

至此，并查集方法结束。

提交记录，第一次哈希表，第二次并查集；

【LeetCode. 825 适龄的朋友】

仔细观察一下这三个条件，我们把age[A] 简写为 a ，把age[B] 简写为 b ，那么如果 a 可以向 b 发送邀请的话，必须同时满足下面三个条件：

• a <= 2*b -15
• a >= b
• a >= 100 && b <= 100

可以发现，如果满足了条件 3 ，那么一定会满足条件 2 ，所以最终只需要满足 b <= a && 2*b -15 >= a 就行了。

第一步，统计每个存在的年龄的人数；

第二步，递归计算 sum；

第三步，根据上述思路写出表达式；

vector<int> count(121 , 0) , sum(121 , 0);
        int n = ages.size();
        for (int i = 0; i < n; i++) {
            count[ages[i]] ++;
        }
        for (int j = 1; j < 121; j++) {
            sum[j] = sum[j-1] + count[j];
        }
        int res = 0;
        for (int b = 15; b < 121; b++) {
            res += count[b] * (sum[min(120 , 2*b - 15)] - sum[b - 1] - 1);
        }
        return res;

提交记录：