C++中将数组划分成K个连续数字的集合

假设我们有一个整数数组nums和一个正整数k，我们需要找出是否可以将此数组划分为k个连续数字的集合。如果可以，则返回True，否则返回False。例如，如果输入是[1,2,3,3,4,4,5,6]且k = 4，则输出为true。这是因为我们可以将数组划分为[1,2,3,4]和[3,4,5,6]。

为了解决这个问题，我们将遵循以下步骤：

  • 创建一个map m，设置n := nums数组的大小
  • 对于nums中的每个元素e
    • 将m[e]增加1
  • cnt := 0
  • 对nums数组进行排序
  • 对于i从0到n
    • x := nums[i]
    • 如果m[x – 1] = 0且m[x] > 0
      • l := k
      • 当k > 0时
        • 如果m[x] > 0，则将m[k]的值减少1，否则返回false
        • 将x和cnt增加1，并将k减少1
      • k := l
  • 当cnt = n时返回true，否则返回false

让我们看下面的实现来更好地理解：

示例

在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool isPossibleDivide(vector<int>& nums, int k) {
      map <int, int> m;
      int n = nums.size();
      for(int i = 0; i < n; i++){
         m[nums[i]]++;
      }
      int cnt = 0;
      sort(nums.begin(), nums.end());
      for(int i = 0; i < n; i++){
         int x = nums[i];
         if(m[x - 1] == 0 && m[x] > 0){
            int l = k;
            while(k>0){
               if(m[x] > 0){
                  m[x]--;
            } else return false;
               x++;
               k--;
               cnt++;
            }
            k = l;
         }
      }
     return cnt == n;
   }
};
main(){
   vector<int> v = {1,2,3,3,4,4,5,6};
   Solution ob;
   cout << (ob.isPossibleDivide(v, 4));
}

输入

[1,2,3,3,4,4,5,6]
4

输出

1

更新于：2020年5月2日

229 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告