สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม nums และจำนวนเต็มบวก k เราต้องค้นหาว่าเป็นไปได้หรือไม่ที่จะแบ่งอาร์เรย์นี้เป็นชุดของตัวเลข k ที่เรียงกัน ดังนั้นเราต้องคืนค่า True หากเป็นไปได้ มิฉะนั้นให้คืนค่า False ดังนั้นหากอินพุตเป็น [1,2,3,3,4,4,5,6] และ k =4 เอาต์พุตจะเป็นจริง นั่นก็เพราะว่า เราสามารถแบ่งอาร์เรย์ออกเป็น [1,2,3,4] และ [3,4,5,6]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างหนึ่งแผนที่ m ตั้งค่า n :=ขนาดของอาร์เรย์ nums
- สำหรับแต่ละองค์ประกอบ e เป็น nums
- เพิ่ม m[e] ขึ้น 1
- cnt :=0
- จัดเรียง nums array
- สำหรับฉันอยู่ในช่วง 0 ถึง n
- x :=nums[i]
- ถ้า m[x – 1] =0 และ m[x]> 0
- l :=k
- ในขณะที่ k> 0
- ถ้า m[x]> 0 ให้ลดค่าของ m[k] ลง 1 มิฉะนั้นจะคืนค่าเป็นเท็จ
- เพิ่ม x และ cnt ขึ้น 1 และลด k ขึ้น 1
- k :=ล
- คืนค่า จริง เมื่อ cnt =n มิฉะนั้น เท็จ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
