하위 배열 Leetcode 솔루션을 반대로하여 두 배열을 동일하게 만들기  


난이도 쉽게
자주 묻는 질문 페이스북 서비스
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions

하위 배열을 뒤집어 두 배열을 동일하게 만드는 문제 Leetcode Solution은 배열. 그중 하나는 대상 배열이고 다른 하나는 입력 배열입니다. 입력 배열을 사용하여 대상 배열을 만들어야합니다. 입력 배열의 하위 배열을 뒤집을 수 있습니다. 그러나 입력 배열의 요소는 변경할 수 없습니다. 조작을 수행하는 방법을 찾을 필요가 없습니다. 가능하면 true를 반환하고 그렇지 않으면 false를 반환합니다. 따라서 평소처럼 솔루션에 깊이 들어가기 전에 몇 가지 예를 살펴 보겠습니다.

하위 배열 Leetcode 솔루션을 반대로하여 두 배열을 동일하게 만들기

target = [1,2,3,4], arr = [2,4,1,3]
true

설명 : 첫 번째 하위 배열을 인덱스 0에서 2로 뒤집은 다음 하위 배열을 1에서 2로 반대로 바꿀 수 있습니다. 결국 인덱스 2에서 3으로 반전합니다. 이렇게하면 대상 배열을 만들 수 있습니다. . 위의 이미지를 보면 더 잘 이해할 수 있습니다.

하위 배열 Leetcode 솔루션을 반대로하여 두 배열을 동일하게 만드는 방법  

계산 방법을 사용하여 문제를 쉽게 해결할 수 있습니다. 계산 방법은 표준 알고리즘 중 일부입니다. 카운트 정렬과 다른 많은 질문에서 사용됩니다. 그래서 여기서 우리는 대상 배열의 요소 수를 유지합니다. 그런 다음 입력 배열의 요소를 탐색합니다. 요소를 만나면 빈도 또는 개수 배열에서 개수를 줄입니다. 이 작업 중에 인덱스가 음수 값을 보유하면 false를 반환합니다.

참조
1의 개수가 0의 개수보다 하나 더 많은 가장 긴 부분 배열

주파수 배열의 음수는 입력 배열의 요소 개수가 더 크다는 것을 나타냅니다. 하지만 이렇게하면 문제가 어떻게 해결됩니까? 관찰을 알면 대답은 간단합니다. 일단 하위 배열의 반전을 수행하려고합니다. 원하는 위치에 입력 배열의 모든 요소를 ​​배치 할 수 있다는 것을 쉽게 알아낼 수 있습니다. 따라서이 규칙을 사용하여 대상 배열의 요소가 입력 배열의 요소와 동일한 지 확인해야합니다.

하위 배열 Leetcode 솔루션을 반대로하여 두 배열을 동일하게 만드는 코드  

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

bool canBeEqual(vector<int>& target, vector<int>& arr) {
    vector<int> cnt(1001, 0);
    for(int i=0;i<target.size();i++)
        ++cnt[target[i]];
    for (int i=0;i<arr.size();i++) {
        if (--cnt[arr[i]] < 0) {
            return false;
        }
    }
    return true;
}

int main(){
    vector<int> target = {1, 2, 3, 4};
    vector<int> arr = {2, 3, 1, 4};
    cout<<(canBeEqual(target, arr) ? "true" : "false");
}
true

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static boolean canBeEqual(int[] target, int[] arr) {
        int[] cnt = new int[1001];
        for(int i=0;i<target.length;i++)
            ++cnt[target[i]];
        for (int i=0;i<arr.length;i++) {
            if (--cnt[arr[i]] < 0) {
                return false;
            }
        }
        return true;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] target = {1, 2, 3, 4};
      int[] arr = {2, 3, 1, 4};
      System.out.print(canBeEqual(target, arr) ? "true" : "false");
  }
}
true

복잡성 분석  

시간 복잡성

의 위에), 배열의 모든 요소를 ​​순회하기 때문입니다.

공간 복잡성

O (1), 일정한 크기의 주파수 또는 개수 배열을 사용했기 때문입니다.

1