1296-划分数组为连续的数字的集合.md

1296-划分数组为连续的数字的集合

原题 给你一个整数数组  nums  和一个正整数  k，请你判断是否可以把这个数组划分成一些由  k  个连续数字组成的集合。 如果可以，请返回 true；否则，返回 false。

输入：nums = [1,2,3,3,4,4,5,6], k = 4 输出：true 解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3 输出：true 解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。

解法

看到官方解法中的说明就懂了，

我们首先考虑数组 nums 中最小的数 a0，显然 a0 一定是某个集合的最小值，且这个集合包含 [a0, a0 + 1, ..., a0 + k - 1] 共 k 个数，因此我们划分出了一个集合，可以将这 k 个数从 nums 中移除。我们接着考虑数

组 nums 剩余元素中最小的数 a1，同理 a1 也是某个集合的最小值，且这个集合包含 [a1, a1 + 1, ..., a1 + k - 1] 共 k 个数，我们同样划分出了一个集合，并将这 k 个数从 nums 中移除。

解法一

原题中翻了下各种解法，都没有我的容易看懂

const isPossibleDivide = function (nums, k) {
  if (nums.length % k !== 0) {
    return false;
  }
  return divide(nums, k);
};

const divide = function (nums, count) {
  let min = Math.min.apply(Math, nums);
  for (let i = 0; i < count; i++) {
    let index = nums.indexOf(min);
    if (index > -1) {
      min = min + 1;
      nums.splice(index, 1);
    } else {
      return false;
    }
  }

  if (!nums.length) {
    return true;
  }
  return divide(nums, count);
};

很自信的第一次在 leetcode 上提交了我的解法，提交结果是什么呢？我日...

执行用时 :9160 ms, 在所有 JavaScript 提交中击败了5.55%的用户
内存消耗 :48 MB, 在所有 JavaScript 提交中击败了100.00%的用户

解法二

我这里使用的事递归加上 for 循环，看了下官方的解法使用了两个 for循环，想着我的也能改

const isPossibleDivide = function (nums, k) {
  if (nums.length % k !== 0) {
    return false;
  }

  for (let i = 0, count = nums.length / k; i < count; i++) {
    let min = Math.min.apply(Math, nums);
    for (let j = 0; j < k; j++) {
      let index = nums.indexOf(min);
      if (index > -1) {
        min = min + 1;
        nums.splice(index, 1);
      } else {
        return false;
      }
    }
  }

  return true;
};

提交测试了一下，就没多大变化，还是得优化下核心解决办法

执行用时 :8532 ms, 在所有 JavaScript 提交中击败了5.55%的用户
内存消耗 :47.4 MB, 在所有 JavaScript 提交中击败了100.00%的用户

执行耗时多，也就是不需要把所有的都执行一遍，要么排查所有的异常然后退出，要么就需要对循环的条件进行筛选，

解法三

按照网友的解法 写了下

const isPossibleDivide = function (nums, k) {
  let map = new Map();
  for (let num of nums) {
    map.set(num, map.has(num) ? map.get(num) + 1 : 1);
  }

  for (let num of nums) {
    if (map.get(num) === 0) {
      continue;
    }

    // 找到 nums 中的最小值
    // 还是使用 Math.min.apply(Math, nums] 更好理解，是更好理解，但不调用 Math 库是不是会快一点？
    while (map.get(--num) > 0);
    // 因为num已经得到了，就直接从 ++nums 开始算，后面的循环k 也就从 1 开始了
    ++num;

    const count = map.get(num);
    for (let i = 1; i < k; ++i) {
      const nextCount = map.get(num + i);

      if (nextCount === undefined || nextCount < count) {
        return false;
      }

      map.set(num + i, nextCount - count);
    }
    map.set(num, 0);
  }
  return true;
};

执行结果，真的有和我的那个少那么久吗？是不是因为 map 本身的操作就比数组快？

执行用时 :120 ms, 在所有 JavaScript 提交中击败了83.33%的用户
内存消耗 :53 MB, 在所有 JavaScript 提交中击败了100.00%的用户