Сделайте два массива равными, переставив подмассивы в решении Leetcode


Сложный уровень Легко
Часто спрашивают в Facebook
массив

Задача сделать два массива равными, перевернув подмассивы. Leetcode Solution предоставляет нам два массивы. Один из них является целевым массивом, а другой - входным. Используя входной массив, нам нужно сделать целевой массив. Мы можем перевернуть любой подмассив во входном массиве. Но мы не можем изменить элементы входного массива. Нам не нужно искать способ выполнения манипуляции. Верните true, если возможно, иначе false. Итак, как обычно, прежде чем углубляться в решение, давайте взглянем на несколько примеров.

Сделайте два массива равными, переставив подмассивы в решении Leetcode

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

Объяснение: Мы можем перевернуть первый подмассив с индекса 0 на 2, затем мы перевернем подмассив с 1 на 2. В конце мы перевернем индекс 2 на 3. И таким образом мы можем сделать целевой массив . Это можно лучше понять, взглянув на изображение выше.

Подход к равенству двух массивов путем обращения подмассивов Решение Leetcode

Проблему легко решить с помощью счетного метода. Метод подсчета является одним из стандартных алгоритмов. Он используется при сортировке по количеству, а также во многих других вопросах. поэтому здесь мы ведем подсчет элементов из целевого массива. Затем мы просматриваем элементы входного массива. Когда мы встречаем какой-либо элемент, мы уменьшаем его счетчик от массива частоты или счетчика. Если каким-то образом во время этой операции какой-либо индекс содержит отрицательное значение, мы возвращаем false.

Отрицательный счетчик в частотном массиве показывает, что входной массив имеет большее количество элемента. Но как это решить проблему? Ответ прост, если вы знаете это наблюдение. Как только вы попытаетесь выполнить несколько разворотов подмассивов. Вы можете легко понять, что можете разместить любой элемент входного массива в любом месте, где захотите. Итак, используя это правило, нам нужно проверить, совпадают ли элементы в целевом массиве с элементами входного массива.

Код для приведения двух массивов в равенство путем обращения подмассивов Решение 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

Java-код

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

Анализ сложности

Сложность времени

НА), потому что мы проходим по всем элементам массивов.

Космическая сложность

О (1), потому что мы использовали частоту постоянного размера или массив счетчиков.