通过反转子阵列Leetcode解决方案使两个阵列相等


难度级别 易得奖学金
经常问 Facebook
排列

通过反转子阵列使两个阵列相等的问题Leetcode解决方案为我们提供了两个 数组。 其中一个是目标数组,另一个是输入数组。 使用输入数组,我们需要制作目标数组。 我们可以反转输入数组中的任何子数组。 但是我们不能更改输入数组的元素。 我们不需要找到一种方法来执行操作。 如果可能,则返回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

复杂度分析

时间复杂度

上), 因为我们遍历了数组的所有元素。

空间复杂度

O(1), 因为我们使用了固定大小的频率或计数数组。