გააკეთე ორი მასივი ტოლი ქვე-მასივების Leetcode ამოხსნის შეცვლით


Რთული ტური Easy
ხშირად ეკითხებიან Facebook
Array

პრობლემა გააკეთეთ ორი მასივი ტოლი ქვე-მასივების შეცვლის გზით Leetcode Solution გვაძლევს ორს მასივები. ერთი მათგანი არის სამიზნე მასივი, ხოლო მეორე - შეყვანის მასივი. შეყვანის მასივის გამოყენებით, ჩვენ უნდა გავაკეთოთ სამიზნე მასივი. შეგვიძლია შევადგინოთ მასივი ნებისმიერი ქვე-მასივი. მაგრამ ჩვენ არ შეგვიძლია შევცვალოთ შეყვანის მასივის ელემენტები. ჩვენ არ გვჭირდება იმის მოძებნა, თუ როგორ უნდა შესრულდეს მანიპულირება. დააბრუნე მართალი, თუ შესაძლებელია სხვა მცდარია ასე რომ, როგორც ყოველთვის ხსნარში სიღრმეში ჩასვლამდე, გადავხედოთ რამდენიმე მაგალითს.

გააკეთე ორი მასივი ტოლი ქვე-მასივების Leetcode ამოხსნის შეცვლით

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

განმარტება: პირველი ქვე-მასივის შეცვლა შეგვიძლია ინდექსიდან 0-დან 2-მდე, შემდეგ ქვე-მასივის შეცვლა 1-დან 2-მდე. საბოლოოდ, ჩვენ უკუვადგენთ ინდექსს 2-დან 3. ამ გზით, შეგვიძლია გავაკეთოთ სამიზნე მასივი . ეს უკეთესად შეიძლება გავიგოთ ზემოთ მოცემული სურათის თვალიერებით.

მიახლოება ორი მასივის ტოლფასი ქვე-მასივების შეცვლა Leetcode Solution- ით

პრობლემის მოგვარება მარტივია დათვლის მეთოდის გამოყენებით. დათვლის მეთოდი სტანდარტული ალგორითმებია. იგი გამოიყენება როგორც რაოდენობის დალაგების, ასევე ბევრ სხვა კითხვაში. აქ ჩვენ ვიცავთ ელემენტების რაოდენობას სამიზნე მასივიდან. შემდეგ ჩვენ გადავკვეთთ შეყვანის მასივის ელემენტებს. როდესაც რაიმე ელემენტს ვაწყდებით, ამცირებთ მის რაოდენობას სიხშირის ან მასის მასივიდან. თუ როგორმე ამ ოპერაციის დროს, ნებისმიერი ინდექსი შეიცავს უარყოფით მნიშვნელობას, ჩვენ ვუბრუნებთ ყალბი

უარყოფითი რიცხვი სიხშირის მასივში აჩვენებს, რომ შეყვანის მასივს უფრო დიდი რაოდენობა აქვს ელემენტისთვის. როგორ ამ პრობლემას წყვეტს ამის გაკეთება? პასუხი მარტივია, თუ დაკვირვება გეცოდინებათ. მას შემდეგ, რაც თქვენ შეეცდებით შეასრულოთ ქვე-მასივების შეცვლა. მარტივად შეგიძლიათ გაერკვიოთ, რომ შეყვანის მასივის ნებისმიერი ელემენტის განთავსება შეგიძლიათ ნებისმიერ ადგილას, სადაც გსურთ. ამ წესის გამოყენებით უნდა შეამოწმოთ სამიზნე მასივის ელემენტები იგივეა, რაც შეყვანის მასივში.

ორი მასივის ტოლფასი კოდექსი ქვე-მასივების Leetcode Solution შეცვლის გზით

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 (N), რადგან ჩვენ გადავკვეთთ მასივების ყველა ელემენტს.

სივრცის სირთულე

O (1), რადგან ჩვენ გამოვიყენეთ მუდმივი ზომის სიხშირე ან თვლის მასივი.