Leetcode шийдлийн дэд массивыг буцааж хоёр массивыг тэнцүү болго


Хэцүү байдлын түвшин Easy
Байнга асуудаг Facebook-ийн
Array

Leetcode шийдлийн дэд массивыг буцааж хоёр массивыг тэнцүү болгох асуудал бидэнд хоёрыг өгдөг массивууд. Тэдгээрийн нэг нь зорилтот массив, нөгөө нь оролтын массив юм. Оруулах массивыг ашиглан бид зорилтот массивыг хийх хэрэгтэй. Бид оруулах массивын аль ч дэд массивыг буцааж болно. Гэхдээ бид оролтын массивын элементүүдийг өөрчилж чадахгүй. Манипуляцийг хэрхэн яаж хийх арга замыг олох шаардлагагүй. Боломжтой бол үнэнийг буцаана уу. Тиймээс, уусмал руу гүн гүнзгий шумбахаасаа өмнө хэд хэдэн жишээг авч үзье.

Leetcode шийдлийн дэд массивыг буцааж хоёр массивыг тэнцүү болго

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

Тайлбар: Бид эхний дэд массивыг 0-ээс 2-р индексээс буцааж, дараа нь дэд массивыг 1-ээс 2 хүртэл эргүүлж болно. Эцэст нь 2-оос 3-р индексийг буцааж оруулна. Ингэснээр бид зорилтот массивыг хийж чадна. . Дээрх зургийг харснаар илүү сайн ойлгогдож болно.

Leetcode шийдлийн дэд массивыг буцаах замаар хоёр массивыг тэнцүү болгох арга

Асуудлыг тоолох аргыг ашиглан хялбархан шийдвэрлэх боломжтой. Тоолох арга бол зарим стандарт алгоритмууд юм. Энэ нь тоолох төрөл болон бусад олон асуултанд хэрэглэгддэг. Тиймээс бид зорилтот массиваас элементүүдийн тоог хадгалдаг. Дараа нь бид оролтын массивын элементүүдийг туулдаг. Аливаа элементтэй тулгарах үед бид түүний тоог давтамж эсвэл тоолох массиваас бууруулдаг. Хэрэв энэ үйл ажиллагааны явцад ямар нэгэн индекс сөрөг утгатай байвал бид буцаана.

Давтамжийн массив дахь сөрөг тоо нь оролтын массив нь элементийн хувьд илүү том тоололтой болохыг харуулж байна. Гэхдээ үүнийг хийснээр асуудлыг хэрхэн шийддэг вэ? Ажиглалтыг мэдсэний дараа хариулт нь энгийн байдаг. Нэгэнт дэд массивын буцаалтыг хийхийг оролдоод үзээрэй. Та хүссэн массивынхаа аль ч элементийг хүссэн газартаа хаана ч байрлуулж болохыг хялбархан мэдэж болно. Тиймээс энэхүү дүрмийг ашиглан зорилтот массив дахь элементүүд оролтын массивтай ижил эсэхийг шалгах хэрэгтэй.

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 (N), Учир нь бид массивын бүх элементүүдийг дайран өнгөрдөг.

Сансрын нарийн төвөгтэй байдал

O (1), Учир нь бид тогтмол хэмжээтэй давтамж эсвэл тоолох массив ашигласан.