資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 次瀏覽
廣告