桶排序

对于0-1000 ，用1001个桶简单版

或者用10个桶0-9，先按各位装桶，然后依（桶）次放回，然后再按十位放桶，放回，然后百位。

也就是基数排序

https://www.cnblogs.com/lqerio/p/11901828.html

Leetcode41

设数组长度为n

那么答案必在 1-n+1的范围内。那么一个萝卜一个坑

先做预处理。类似于桶排序，把正确的数放在正确的位置。

遍历数组，对于i+1，若i+1在1-n内，应该放在nums[i]的位置上

if (nums[i] <= 0 || nums[i] > nums.size() || nums[i] == nums[nums[i] - 1]) 跳过。因为没有正确的位置或者已经在正确的位置上了

然后遍历，从0开始到n，若nums[i]!=i+1，就输出i+1. 因为这时候，通过上面的预处理，说明不存在i+1这个数。

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        for (int i = 0; i < nums.size(); i++) {

            while (nums[i] != i + 1) {

                if (nums[i] <= 0 || nums[i] > nums.size() || nums[i] == nums[nums[i] - 1])

                    break;

                int idx = nums[i] - 1;

                nums[i] = nums[idx];

                nums[idx] = idx + 1;

            }

        }

        for (int i = 0; i < nums.size(); i++) {

            if (nums[i] != (i + 1)) {

                return (i + 1);

            }

        }

        return (nums.size() + 1);

        }

};

然后官方题解为hash表

首先可知结果最大为n+1，n为数组长度

预处理：

1.先判断是否有1，无则输出1

2.否则遍历数组，对大于n或者小于1的数改为1

3.然后遍历数组，对于num[k]=i，将nums[i]设置为负数。 nums[i]<0说明数组中存在i （用自己做hash表）

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

    int n = nums.size();

    int flag = 0;  // 1 not exist

    for (int i = 0; i < n; i++)

      if (nums[i] == 1) {

        flag=1;

        break;

      }

    if (!flag)

      return 1;

    if (n == 1)

      return 2;

    // 用 1 替换负数，0，和大于 n 的数

    // 在转换以后，nums 只会包含1-n

    for (int i = 0; i < n; i++)

      if ((nums[i] <= 0) || (nums[i] > n))

        nums[i] = 1;

    // 使用索引和数字符号作为检查器

    // 例如，如果 nums[1] 是负数表示在数组中出现了数字 `1`

    // 如果 nums[2] 是正数 表示数字 2 没有出现

    for (int i = 0; i < n; i++) {

      int a = abs(nums[i]);

      // 如果发现了一个数字 a - 改变第 a 个元素的符号

      // 注意重复元素只需操作一次

      if (a == n)

        nums[0] = - abs(nums[0]);

      else

        nums[a] = - abs(nums[a]);

    }

    // 现在第一个正数的下标就是第一个缺失的数

    for (int i = 1; i < n; i++) {

      if (nums[i] > 0)

        return i;

    }

    if (nums[0] > 0)

      return n;

    return n + 1;

        }

};

巴特西

桶排序 && leetcode 41

桶排序

也就是基数排序

Leetcode41

最新文章

热门文章