정렬을 감안할 때 정렬(오름차순으로) 모든 하위 시퀀스에 연속 번호가 포함되도록 배열을 1보다 큰 길이의 하위 시퀀스 3 개 이상으로 분할 할 수 있는지 확인합니다.
차례
예
입력:
arr [] = {1,2,3,3,4,5}
출력:
참된
설명 :
배열은 다음과 같이 2 개의 하위 시퀀스로 나눌 수 있습니다.
sub1 [] = {1, 2, 3}
sub2 [] = {3, 4, 5}
입력:
arr [] = {Z1, 2, 3, 3, 4, 4, 5, 5}
출력:
참된
설명 :
연속적인 하위 시퀀스는 다음과 같습니다.
sub1 [] = {1, 2, 3, 4, 5}
sub2 [] = {3, 4, 5}
연속적인 하위 시퀀스로 배열을 분할하는 순진한 접근 방식
주어진 배열의 arr [i] 요소에 대해 새 하위 시퀀스를 형성하거나 (arr [i] – 1)로 끝나는 하위 시퀀스에 추가 될 수 있습니다.
항상 낫다 지원 새로운 서브 시퀀스를 형성하기 위해 새로운 서브 시퀀스를 형성하는 것은 길이가 1 미만인 일부 서브 시퀀스를 초래할 수 있습니다. (arr [i] – XNUMX)로 끝나는 하위 시퀀스가 없으면 새 하위 시퀀스를 형성하는 것 외에는 옵션이 없습니다.
현재 요소를 수용 할 수있는 하위 시퀀스가 두 개 이상있는 경우 항상 요소 수가 가장 적은 하위 시퀀스에 현재 요소를 추가합니다. 이렇게하면 길이가 3 미만인 하위 시퀀스를 최소화 할 수 있습니다.
암호알고리즘
- 배열의 첫 번째 요소는 항상 새 하위 시퀀스를 형성합니다.
- 인덱스 1 (0 기반 인덱싱)부터 배열을 탐색합니다.
- 현재 요소를 수용 할 수있는 하위 시퀀스가 있는지 확인합니다. arr [i] 요소를 (arr [i] – 1)로 끝나는 하위 시퀀스에 추가 할 수 있습니다.
- 현재 요소를 수용 할 수있는 하위 시퀀스가없는 경우 새 하위 시퀀스를 형성합니다.
- 그렇지 않으면 현재 요소를 수용 할 수있는 최소 크기로 하위 시퀀스를 선택하고 선택한 하위 시퀀스에 현재 요소를 추가합니다.
- 배열을 순회 한 후 길이가 3 미만인 하위 시퀀스가 있는지 확인하고, 그렇다면 false를 반환하고 그렇지 않으면 true를 반환합니다.
연속적인 하위 시퀀스로 분할 배열을위한 JAVA 코드
import java.util.ArrayList;
public class SplitTheArrayIntoConsecutievSubsequences {
private static boolean isPossible(int[] arr) {
// If the lenght of arr is less than 3, it is not possible to split the array
if (arr == null || arr.length < 3) {
return false;
}
int n = arr.length;
// List of subsequences
ArrayList<ArrayList<Integer>> al = new ArrayList<>();
// First element always forms a new subsequence
ArrayList<Integer> eles = new ArrayList<Integer>();
eles.add(arr[0]);
al.add(eles);
// Traverse the array starting from index 1
for (int i = 1; i < n; i++) {
// Required position of subsequence that can accommodate the current element
int pos = -1;
// Size of required subsequence
int size = -1;
// Check if there is some subsequence that can accommodate the current element
for (int j = 0; j < al.size(); j++) {
// A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
if (al.get(j).get(al.get(j).size() - 1) + 1 == arr[i]) {
if (pos == -1) {
pos = j;
size = al.get(j).size();
} else {
// Select the subsequence with minimum size
if (al.get(j).size() < size) {
pos = j;
size = al.get(j).size();
}
}
}
}
// If there is no subsequence that can accommodate the current element
// form a new subsequence
if (pos == -1) {
ArrayList<Integer> newAL = new ArrayList<>();
newAL.add(arr[i]);
al.add(newAL);
} else {
// else add it to the required subsequence
al.get(pos).add(arr[i]);
}
}
for (int i = 0; i < al.size(); i++) {
// if there is some subsequence of length less than 3, return false
if (al.get(i).size() < 3) {
return false;
}
}
// No subsequence of length less than 3, return true
return true;
}
public static void main(String[] args) {
// Example 1
int arr1[] = new int[]{1, 2, 3, 3, 4, 5};
System.out.println(isPossible(arr1));
// Example 2
int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};
System.out.println(isPossible(arr2));
// Example 3
int arr3[] = new int[]{1, 2, 3, 4, 4, 5};
System.out.println(isPossible(arr3));
}
}
true true false
연속 하위 시퀀스로 배열 분할을위한 C ++ 코드
#include<bits/stdc++.h>
using namespace std;
bool isPossible(int *arr, int n) {
if (n < 3) {
return false;
}
// List of subsequences
vector<vector<int>> v;
// First element always forms a new subsequence
vector<int> eles;
eles.push_back(arr[0]);
v.push_back(eles);
// Traverse the array starting from index 1
for (int i = 1; i < n; i++) {
// Required position of subsequence that can accommodate the current element
int pos = -1;
// Size of required subsequence
int size = -1;
// Check if there is some subsequence that can accommodate the current element
for (int j = 0; j < v.size(); j++) {
// A subsequence ending at (arr[i] - 1) can accommodate the element arr[i]
if (v[j][v[j].size() - 1] + 1 == arr[i]) {
if (pos == -1) {
pos = j;
size = v[j].size();
} else {
// Select the subsequence with minimum size
if (v[j].size() < size) {
size = v[j].size();
pos = j;
}
}
}
}
// If there is no subsequence that can accommodate the current element
// form a new subsequence
if (pos == -1) {
vector<int> newV;
newV.push_back(arr[i]);
v.push_back(newV);
} else {
v[pos].push_back(arr[i]);
}
}
for (int i = 0; i < v.size(); i++) {
if (v[i].size() < 3) {
return false;
}
}
return true;
}
int main() {
// Example 1
int arr1[] = {1, 2, 3, 3, 4, 5};
if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 3
int arr3[] = {1, 2, 3, 4, 4, 5};
if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
true true false
복잡성 분석
시간 복잡성 = 의 위에2)
공간 복잡성 = O (N)
연속적인 하위 시퀀스로 어레이를 분할하기위한 최적의 접근 방식
arr [i] 요소의 경우 새 하위 시퀀스를 형성하거나 (arr [i] – 1)로 끝나는 다른 하위 시퀀스에 추가 할 수 있습니다. arr [i]를 수용 할 수있는 하위 시퀀스가 두 개 이상있는 경우 추가합니다. 최소 길이의 하위 시퀀스에.
세 가지 유형의 하위 시퀀스 길이 만 중요합니다. 즉, p1, c2, p3, c1, p1 및 c2으로 표시되는 길이 2, 길이 3 및 길이 3보다 큰 하위 시퀀스, 여기서 p는 이전을 의미하고 c는 현재를 의미합니다.
모든 숫자에 대해 배열에서 발생하는 횟수를 먼저 세고, 길이 1과 2의 모든 하위 시퀀스에 분산 될 수 있는지 확인하고, 불가능한 경우 현재 숫자가 길이 1의 하위 시퀀스를 확장 할 수없는 경우 즉시 false를 반환하거나 2, 배열이 정렬 될 때 숫자가 없습니다. 따라서 끝에 길이 1 또는 2의 일부 하위 시퀀스가 남아 있습니다.
그렇지 않으면 길이 1의 모든 하위 시퀀스가 길이 2의 하위 시퀀스로 변환되고, 길이 2는 길이 3으로 변환되며, 나머지 요소는 길이 3 이상의 하위 시퀀스에 추가됩니다. 여전히 일부 요소가 분산되어 있지 않으면 길이 1의 하위 시퀀스에 기여합니다. 길이 3 이상에 기여하는 요소 만 새 길이 3 하위 시퀀스에 추가됩니다.
마지막에 길이 1이없고 길이 2 하위 시퀀스가 true를 반환하고 그렇지 않으면 false를 반환합니다.
JAVA 코드
public class SplitArrayIntoConsecutiveSubsequences {
private static boolean isPossible(int[] arr) {
int n = arr.length;
if (n < 3) {
return false;
}
int p1 = 0, p2 = 0, p3 = 0;
int c1 = 0, c2 = 0, c3 = 0;
int i = 0;
// prev denotes previous element
// curr denotes current element
int prev = 0, curr = 0;
// Traverse the array
while (i < n) {
// Current becomes previous
p1 = c1;
p2 = c2;
p3 = c3;
prev = curr;
curr = arr[i];
int count = 0;
// Count the frequency of current element
while (i < n && arr[i] == curr) {
i++;
count++;
}
if (prev + 1 == curr) {
// if element cannot be spread across subsequences of length 1 and 2
if (count < p1 + p2) {
// return false immediately
return false;
}
// Update c1, c2, c3 as described
c1 = Math.max(0, count - (p1 + p2 + p3));
c2 = p1;
c3 = p2 + Math.min(p3, count - (p1 + p2));
} else {
// this element cannot be spread across any subsequence
if (p1 != 0 || p2 != 0) {
// if there is any subsequence of length 1 or 2
// return false immediately
return false;
}
// Update c1, c2, c3 as described
c1 = count;
c2 = 0;
c3 = 0;
}
}
// if there are no length 1 and length 2 subsequences return true, else return false
return (c1 == 0 && c2 == 0);
}
public static void main(String[] args) {
// Example 1
int arr1[] = new int[]{1, 2, 3, 3, 4, 5};
System.out.println(isPossible(arr1));
// Example 2
int arr2[] = new int[]{1, 2, 3, 3, 4, 4, 5, 5};
System.out.println(isPossible(arr2));
// Example 3
int arr3[] = new int[]{1, 2, 3, 4, 4, 5};
System.out.println(isPossible(arr3));
}
}
true true false
C ++ 코드
#include<bits/stdc++.h>
using namespace std;
bool isPossible(int *arr, int n) {
if (n < 3) {
return false;
}
int p1 = 0, p2 = 0, p3 = 0;
int c1 = 0, c2 = 0, c3 = 0;
int i = 0;
// prev denotes previous element
// curr denotes current element
int prev = 0, curr = 0;
// Traverse the array
while (i < n) {
// Current becomes previous
p1 = c1;
p2 = c2;
p3 = c3;
prev = curr;
curr = arr[i];
int count = 0;
// Count the frequency of current element
while (i < n && arr[i] == curr) {
i++;
count++;
}
if (prev + 1 == curr) {
// if element cannot be spread across subsequences of length 1 and 2
if (count < p1 + p2) {
// return false immediately
return false;
}
// Update c1, c2, c3 as described
c1 = std::max(0, count - (p1 + p2 + p3));
c2 = p1;
c3 = p2 + std::min(p3, count - (p1 + p2));
} else {
// this element cannot be spread across any subsequence
if (p1 != 0 || p2 != 0) {
// if there is any subsequence of length 1 or 2
// return false immediately
return false;
}
// Update c1, c2, c3 as described
c1 = count;
c2 = 0;
c3 = 0;
}
}
// if there are no length 1 and length 2 subsequences return true, else return false
return (c1 == 0 && c2 == 0);
}
int main() {
// Example 1
int arr1[] = {1, 2, 3, 3, 4, 5};
if(isPossible(arr1, sizeof(arr1) / sizeof(arr1[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 2
int arr2[] = {1, 2, 3, 3, 4, 4, 5, 5};
if (isPossible(arr2, sizeof(arr2) / sizeof(arr2[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
// Example 3
int arr3[] = {1, 2, 3, 4, 4, 5};
if (isPossible(arr3, sizeof(arr3) / sizeof(arr3[0]))) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
true true false
복잡성 분석
시간 복잡성 = O (N)
공간 복잡성 = O (1)
