首页 > 编程语言 > 详细

桶排序 && leetcode 41

时间:2019-11-21 01:05:17      阅读:116      评论:0      收藏:0      [点我收藏+]

桶排序

对于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

原文:https://www.cnblogs.com/lqerio/p/11902034.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!