สมมติว่าเรามีจำนวนอาร์เรย์ที่เรียงลำดับจากน้อยไปหามาก เราต้องคืนค่า จริง หากเราสามารถแบ่งออกเป็น 1 ลำดับย่อยขึ้นไป โดยที่แต่ละส่วนย่อยประกอบด้วยจำนวนเต็มที่ต่อเนื่องกันและมีความยาวอย่างน้อย 3 ดังนั้นหากอินพุตเป็นเช่น [1,2,3,3,4 4,5,5] แล้วผลลัพธ์จะเป็น True เนื่องจากเรามีสองลำดับต่อเนื่องกัน ได้แก่ [1,2,3,4,5] และ [3,4,5]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างแผนที่ m และเก็บความถี่ของ nums เป็น m เก็บขนาดของ nums เป็น m
- cnt :=n
- สำหรับ i ในช่วง 0 ถึง n – 1
- x :=nums[i]
- ถ้า m[x] และ m[x + 1] และ m[x + 2]
- ลด m[x], m[x + 1] และ m[x + 2] ลง 1, เพิ่ม x ขึ้น 3 และลดจำนวนลง 3
- ในขณะที่ m[x]> 0 และ m[x]> m[x – 1]
- ลดลง 1, ลด m[x] 1 และเพิ่ม x 1
- คืนค่า จริง ถ้า cnt เป็น 0 มิฉะนั้น เท็จ
- ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPossible(vector<int>& nums) {
unordered_map <int, int> m;
int n = nums.size();
for(int i = 0; i < n; i++){
m[nums[i]]++;
}
int cnt = n;
for(int i = 0; i < n; i++){
int x = nums[i];
if(m[x] && m[x + 1] && m[x + 2]){
m[x]--;
m[x + 1]--;
m[x + 2]--;
x += 3;
cnt -= 3;
while(m[x] > 0 && m[x] > m[x - 1]){
cnt--;
m[x]--;
x++;
}
}
}
return cnt == 0;
}
};
main(){
vector<int> v = {1,2,3,3,4,4,5,5};
Solution ob;
cout << (ob.isPossible(v));
} อินพุต
[1,2,3,3,4,4,5,5]
ผลลัพธ์
1
