#practiceLinkDiv { 표시: 없음 !중요; }n개의 정수 배열이 주어졌습니다. 작업은 배열에서 최소 수의 요소를 제거하거나 삭제하여 나머지 요소가 동일한 순서로 배치되어 배열을 형성하는 것입니다. 정렬된 순서 증가 .
예:
Input : {5 6 1 7 4}Recommended Practice 정렬된 시퀀스를 만들기 위한 최소 삭제 수 시도해 보세요!
Output : 2
Removing 1 and 4
leaves the remaining sequence order as
5 6 7 which is a sorted sequence.
Input : {30 40 2 5 1 7 45 50 8}
Output : 4
에이 간단한 해결책 제거하는 것이다 모든 하위 시퀀스 하나씩 나머지 요소 집합이 정렬된 순서로 되어 있는지 확인하세요. 이 솔루션의 시간 복잡도는 기하급수적으로 증가합니다.
안 효율적인 접근 방식 의 개념을 사용합니다. 가장 긴 증가 부분 수열의 길이 찾기 주어진 순서의.
연산:
문자열 추가 자바
--> arr be the given array.C++
--> n number of elements in arr .
--> len be the length of longest
increasing subsequence in arr .
-->// minimum number of deletions
min = n - len
// C++ implementation to find // minimum number of deletions // to make a sorted sequence #include
// Java implementation to find // minimum number of deletions // to make a sorted sequence class GFG { /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ static int lis( int arr[] int n ) { int result = 0; int[] lis = new int[n]; /* Initialize LIS values for all indexes */ for (int i = 0; i < n; i++ ) lis[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (int i = 1; i < n; i++ ) for (int j = 0; j < i; j++ ) if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; /* Pick resultimum of all LIS values */ for (int i = 0; i < n; i++ ) if (result < lis[i]) result = lis[i]; return result; } // function to calculate minimum // number of deletions static int minimumNumberOfDeletions(int arr[] int n) { // Find longest // increasing subsequence int len = lis(arr n); // After removing elements // other than the lis we get // sorted sequence. return (n - len); } // Driver Code public static void main (String[] args) { int arr[] = {30 40 2 5 1 7 45 50 8}; int n = arr.length; System.out.println('Minimum number of' + ' deletions = ' + minimumNumberOfDeletions(arr n)); } } /* This code is contributed by Harsh Agarwal */
# Python3 implementation to find # minimum number of deletions to # make a sorted sequence # lis() returns the length # of the longest increasing # subsequence in arr[] of size n def lis(arr n): result = 0 lis = [0 for i in range(n)] # Initialize LIS values # for all indexes for i in range(n): lis[i] = 1 # Compute optimized LIS values # in bottom up manner for i in range(1 n): for j in range(i): if ( arr[i] > arr[j] and lis[i] < lis[j] + 1): lis[i] = lis[j] + 1 # Pick resultimum # of all LIS values for i in range(n): if (result < lis[i]): result = lis[i] return result # Function to calculate minimum # number of deletions def minimumNumberOfDeletions(arr n): # Find longest increasing # subsequence len = lis(arr n) # After removing elements # other than the lis we # get sorted sequence. return (n - len) # Driver Code arr = [30 40 2 5 1 7 45 50 8] n = len(arr) print('Minimum number of deletions = ' minimumNumberOfDeletions(arr n)) # This code is contributed by Anant Agarwal.
// C# implementation to find // minimum number of deletions // to make a sorted sequence using System; class GfG { /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ static int lis( int []arr int n ) { int result = 0; int[] lis = new int[n]; /* Initialize LIS values for all indexes */ for (int i = 0; i < n; i++ ) lis[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (int i = 1; i < n; i++ ) for (int j = 0; j < i; j++ ) if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; /* Pick resultimum of all LIS values */ for (int i = 0; i < n; i++ ) if (result < lis[i]) result = lis[i]; return result; } // function to calculate minimum // number of deletions static int minimumNumberOfDeletions( int []arr int n) { // Find longest increasing // subsequence int len = lis(arr n); // After removing elements other // than the lis we get sorted // sequence. return (n - len); } // Driver Code public static void Main (String[] args) { int []arr = {30 40 2 5 1 7 45 50 8}; int n = arr.Length; Console.Write('Minimum number of' + ' deletions = ' + minimumNumberOfDeletions(arr n)); } } // This code is contributed by parashar.
<script> // javascript implementation to find // minimum number of deletions // to make a sorted sequence /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ function lis(arrn) { let result = 0; let lis= new Array(n); /* Initialize LIS values for all indexes */ for (let i = 0; i < n; i++ ) lis[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (let i = 1; i < n; i++ ) for (let j = 0; j < i; j++ ) if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; /* Pick resultimum of all LIS values */ for (let i = 0; i < n; i++ ) if (result < lis[i]) result = lis[i]; return result; } // function to calculate minimum // number of deletions function minimumNumberOfDeletions(arrn) { // Find longest increasing // subsequence let len = lis(arrn); // After removing elements // other than the lis we // get sorted sequence. return (n - len); } let arr = [30 40 2 5 17 45 50 8]; let n = arr.length; document.write('Minimum number of deletions = ' + minimumNumberOfDeletions(arrn)); // This code is contributed by vaibhavrabadiya117. </script>
// PHP implementation to find // minimum number of deletions // to make a sorted sequence /* lis() returns the length of the longest increasing subsequence in arr[] of size n */ function lis( $arr $n ) { $result = 0; $lis[$n] = 0; /* Initialize LIS values for all indexes */ for ($i = 0; $i < $n; $i++ ) $lis[$i] = 1; /* Compute optimized LIS values in bottom up manner */ for ($i = 1; $i < $n; $i++ ) for ($j = 0; $j < $i; $j++ ) if ( $arr[$i] > $arr[$j] && $lis[$i] < $lis[$j] + 1) $lis[$i] = $lis[$j] + 1; /* Pick resultimum of all LIS values */ for ($i = 0; $i < $n; $i++ ) if ($result < $lis[$i]) $result = $lis[$i]; return $result; } // function to calculate minimum // number of deletions function minimumNumberOfDeletions($arr $n) { // Find longest increasing // subsequence $len = lis($arr $n); // After removing elements // other than the lis we // get sorted sequence. return ($n - $len); } // Driver Code $arr = array(30 40 2 5 1 7 45 50 8); $n = sizeof($arr) / sizeof($arr[0]); echo 'Minimum number of deletions = ' minimumNumberOfDeletions($arr $n); // This code is contributed by nitin mittal. ?> 산출
Minimum number of deletions = 4
시간 복잡도: 에2)
보조 공간: 에)
시간 복잡도는 다음을 찾아 O(nlogn)으로 줄일 수 있습니다. 가장 긴 증가 부분 수열 크기(N Log N)
이 기사는 기고자: 아유시 자우하리 .
접근법#2: 가장 긴 증가 부분 수열 사용
이 문제를 해결하는 한 가지 접근법은 주어진 배열의 가장 긴 증가 부분 수열(LIS)의 길이를 찾아 배열 길이에서 빼는 것입니다. 차이점은 배열을 정렬하는 데 필요한 최소 삭제 횟수를 제공합니다.
자바는 난수를 생성
연산
1. 배열의 가장 긴 증가 부분 수열(LIS)의 길이를 계산합니다.
2. 배열 길이에서 LIS 길이를 뺍니다.
3. 2단계에서 얻은 차이를 출력으로 반환합니다.
#include
import java.util.Arrays; public class Main { public static int minDeletions(int[] arr) { int n = arr.length; int[] lis = new int[n]; Arrays.fill(lis 1); // Initialize the LIS array with all 1's for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (arr[i] > arr[j]) { lis[i] = Math.max(lis[i] lis[j] + 1); } } } return n - Arrays.stream(lis).max().getAsInt(); // Return the number of elements to delete } public static void main(String[] args) { int[] arr = {5 6 1 7 4}; System.out.println(minDeletions(arr)); // Output: 2 } }
def min_deletions(arr): n = len(arr) lis = [1] * n for i in range(1 n): for j in range(i): if arr[i] > arr[j]: lis[i] = max(lis[i] lis[j] + 1) return n - max(lis) arr = [5 6 1 7 4] print(min_deletions(arr))
using System; using System.Collections.Generic; using System.Linq; namespace MinDeletionsExample { class Program { static int MinDeletions(List<int> arr) { int n = arr.Count; List<int> lis = Enumerable.Repeat(1 n).ToList(); // Initialize LIS array with 1 // Calculate LIS values for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (arr[i] > arr[j]) { lis[i] = Math.Max(lis[i] lis[j] + 1); // Update LIS value } } } // Find the maximum length of LIS int maxLength = lis.Max(); // Return the minimum number of deletions return n - maxLength; } // Driver Code static void Main(string[] args) { List<int> arr = new List<int> { 5 6 1 7 4 }; // Call the MinDeletions function and print the result Console.WriteLine(MinDeletions(arr)); // Keep console window open until a key is pressed Console.ReadKey(); } } }
function minDeletions(arr) { let n = arr.length; let lis = new Array(n).fill(1); for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { if (arr[i] > arr[j]) { lis[i] = Math.max(lis[i] lis[j] + 1); } } } return n - Math.max(...lis); } let arr = [5 6 1 7 4]; console.log(minDeletions(arr));
산출
2
시간 복잡도: O(n^2) 여기서 n은 배열 길이입니다.
공간 복잡도: O(n) 여기서 n은 배열의 길이입니다.
접근법#3: 이진 검색 사용
이 접근 방식은 이진 검색을 사용하여 지정된 요소를 하위 시퀀스에 삽입할 올바른 위치를 찾습니다.
연산
1. 입력 목록의 첫 번째 요소로 'sub' 목록을 초기화합니다.
2. 입력 목록의 각 후속 요소에 대해 'sub'의 마지막 요소보다 큰 경우 이를 'sub'에 추가합니다.
3. 그렇지 않으면 이진 검색을 사용하여 'sub'에 요소를 삽입할 올바른 위치를 찾습니다.
4. 필요한 최소 삭제 횟수는 입력 목록의 길이에서 'sub'의 길이를 뺀 값과 같습니다.
#include
import java.util.ArrayList; public class Main { // Function to find the minimum number of deletions to make a strictly increasing subsequence static int minDeletions(ArrayList<Integer> arr) { int n = arr.size(); ArrayList<Integer> sub = new ArrayList<>(); // Stores the longest increasing subsequence sub.add(arr.get(0)); // Initialize the subsequence with the first element of the array for (int i = 1; i < n; i++) { if (arr.get(i) > sub.get(sub.size() - 1)) { // If the current element is greater than the last element of the subsequence // it can be added to the subsequence to make it longer. sub.add(arr.get(i)); } else { int index = -1; // Initialize index to -1 int val = arr.get(i); // Current element value int l = 0 r = sub.size() - 1; // Initialize left and right pointers for binary search // Binary search to find the index where the current element can be placed in the subsequence while (l <= r) { int mid = (l + r) / 2; // Calculate the middle index if (sub.get(mid) >= val) { index = mid; // Update the index if the middle element is greater or equal to the current element r = mid - 1; // Move the right pointer to mid - 1 } else { l = mid + 1; // Move the left pointer to mid + 1 } } if (index != -1) { sub.set(index val); // Replace the element at the found index with the current element } } } // The minimum number of deletions is equal to the difference between the input array size and the size of the longest increasing subsequence return n - sub.size(); } public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>(); arr.add(30); arr.add(40); arr.add(2); arr.add(5); arr.add(1); arr.add(7); arr.add(45); arr.add(50); arr.add(8); int output = minDeletions(arr); System.out.println(output); } }
def min_deletions(arr): def ceil_index(sub val): l r = 0 len(sub)-1 while l <= r: mid = (l + r) // 2 if sub[mid] >= val: r = mid - 1 else: l = mid + 1 return l sub = [arr[0]] for i in range(1 len(arr)): if arr[i] > sub[-1]: sub.append(arr[i]) else: sub[ceil_index(sub arr[i])] = arr[i] return len(arr) - len(sub) arr = [30 40 2 5 1 7 45 50 8] output = min_deletions(arr) print(output)
using System; using System.Collections.Generic; class Program { // Function to find the minimum number of deletions to make a strictly increasing subsequence static int MinDeletions(List<int> arr) { int n = arr.Count; List<int> sub = new List<int>(); // Stores the longest increasing subsequence sub.Add(arr[0]); // Initialize the subsequence with the first element of the array for (int i = 1; i < n; i++) { if (arr[i] > sub[sub.Count - 1]) { // If the current element is greater than the last element of the subsequence // it can be added to the subsequence to make it longer. sub.Add(arr[i]); } else { int index = -1; // Initialize index to -1 int val = arr[i]; // Current element value int l = 0 r = sub.Count - 1; // Initialize left and right // pointers for binary search // Binary search to find the index where the current element // can be placed in the subsequence while (l <= r) { int mid = (l + r) / 2; // Calculate the middle index if (sub[mid] >= val) { index = mid; // Update the index if the middle element is // greater or equal to the current element r = mid - 1; // Move the right pointer to mid - 1 } else { l = mid + 1; // Move the left pointer to mid + 1 } } if (index != -1) { sub[index] = val; // Replace the element at the found index // with the current element } } } // The minimum number of deletions is equal to the difference // between the input list size and the size of the // longest increasing subsequence return n - sub.Count; } // Driver code static void Main() { List<int> arr = new List<int> { 30 40 2 5 1 7 45 50 8 }; int output = MinDeletions(arr); Console.WriteLine(output); Console.ReadLine(); } }
// Function to find the minimum number of deletions to make a strictly increasing subsequence function minDeletions(arr) { let n = arr.length; let sub = []; // Stores the longest increasing subsequence sub.push(arr[0]); // Initialize the subsequence with the first element of the array for (let i = 1; i < n; i++) { if (arr[i] > sub[sub.length - 1]) { // If the current element is greater than the last element of the subsequence // it can be added to the subsequence to make it longer. sub.push(arr[i]); } else { let index = -1; // Initialize index to -1 let val = arr[i]; // Current element value let l = 0 r = sub.length - 1; // Initialize left and right pointers for binary search // Binary search to find the index where the current element can be placed // in the subsequence while (l <= r) { let mid = Math.floor((l + r) / 2); // Calculate the middle index if (sub[mid] >= val) { index = mid; // Update the index if the middle element is greater //or equal to the current element r = mid - 1; // Move the right pointer to mid - 1 } else { l = mid + 1; // Move the left pointer to mid + 1 } } if (index !== -1) { sub[index] = val; // Replace the element at the found index with the current element } } } // The minimum number of deletions is equal to the difference //between the input array size and the size of the longest increasing subsequence return n - sub.length; } let arr = [30 40 2 5 1 7 45 50 8]; let output = minDeletions(arr); console.log(output);
산출
4
시간 복잡도: O(n log n)
보조 공간: O(n)
퀴즈 만들기