ធ្វើអារេពីរស្មើគ្នាដោយបញ្ច្រាសដំណោះស្រាយអារេឡេហ្សិច


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ Facebook
អារេ

បញ្ហាធ្វើឱ្យអារេពីរស្មើគ្នាដោយបញ្ច្រាសអារេ Leetcode ដំណោះស្រាយផ្តល់ឱ្យយើងនូវពីរ អារេ។ មួយក្នុងចំណោមពួកគេគឺជាអារេគោលដៅហើយមួយទៀតគឺអារេបញ្ចូល។ ដោយប្រើអារេបញ្ចូលយើងត្រូវបង្កើតអារេគោលដៅ។ យើងអាចបញ្ច្រាស់អនុជួរណាមួយនៅក្នុងអារេបញ្ចូល។ ប៉ុន្តែយើងមិនអាចផ្លាស់ប្តូរធាតុនៃអារេបញ្ចូលបានទេ។ យើងមិនចាំបាច់រកមធ្យោបាយសម្រាប់របៀបអនុវត្តឧបាយកលនេះទេ។ ត្រឡប់ការពិតបើអាចធ្វើខុសបាន។ ដូច្នេះដូចធម្មតាមុនពេលមុជជ្រៅទៅក្នុងដំណោះស្រាយសូមឱ្យយើងពិចារណាឧទាហរណ៍មួយចំនួន។

ធ្វើអារេពីរស្មើគ្នាដោយបញ្ច្រាសដំណោះស្រាយអារេឡេហ្សិច

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

ការពន្យល់ៈយើងអាចបញ្ច្រាស់អនុជួរទីមួយពីសន្ទស្សន៍ ០ ដល់ ២ បន្ទាប់មកយើងបញ្ច្រាស់អនុជួរពី ១ ដល់ ២ ។ នៅចុងបញ្ចប់យើងប្តូរលិបិក្រម ២ ទៅ ៣ ហើយតាមវិធីនេះយើងអាចបង្កើតអារេគោលដៅ ។ វាអាចត្រូវបានយល់កាន់តែច្បាស់ដោយមើលរូបភាពខាងលើ។

វិធីសាស្រ្តសម្រាប់ធ្វើអារេពីរស្មើគ្នាដោយបញ្ច្រាសដំណោះស្រាយអារេឡេតកូដ

បញ្ហាអាចត្រូវបានដោះស្រាយយ៉ាងងាយស្រួលដោយប្រើវិធីសាស្ត្ររាប់។ វិធីសាស្ត្ររាប់គឺមានក្បួនដោះស្រាយស្តង់ដារមួយចំនួន។ វាត្រូវបានប្រើក្នុងការរាប់ក៏ដូចជានៅក្នុងសំណួរជាច្រើនទៀត។ ដូច្នេះនៅទីនេះយើងរក្សាចំនួនធាតុពីជួរគោលដៅ។ បន្ទាប់មកយើងឆ្លងកាត់ធាតុនៃអារេបញ្ចូល។ នៅពេលយើងជួបប្រទះធាតុណាមួយយើងបន្ថយចំនួនរបស់វាពីប្រេកង់ឬរាប់អារេ។ ប្រសិនបើដូចម្ដេចក្នុងកំឡុងពេលប្រតិបត្តិការនេះសន្ទស្សន៍ណាមួយរក្សាតម្លៃអវិជ្ជមានដែលយើងត្រលប់មកវិញមិនពិត។

ការរាប់អវិជ្ជមាននៅក្នុងអារេប្រេកង់បង្ហាញអារេបញ្ចូលមានចំនួនធំជាងសម្រាប់ធាតុមួយ។ ប៉ុន្តែតើការធ្វើបែបនេះអាចដោះស្រាយបញ្ហាយ៉ាងដូចម្តេច? ចម្លើយគឺសាមញ្ញនៅពេលអ្នកដឹងពីការសង្កេត។ នៅពេលអ្នកព្យាយាមអនុវត្តការបញ្ច្រាសខ្លះនៃអនុរង។ អ្នកអាចដោះស្រាយបានយ៉ាងងាយថាអ្នកអាចដាក់ធាតុណាមួយនៃធាតុបញ្ចូលនៅកន្លែងណាមួយដែលអ្នកចង់បាន។ ដូច្នេះដោយប្រើច្បាប់នេះយើងត្រូវពិនិត្យមើលថាតើធាតុនៅក្នុងអារេគោលដៅគឺដូចគ្នានឹងអារេនៃធាតុបញ្ចូលដែរឬទេ។

លេខកូដសំរាប់ធ្វើអារេពីរស្មើគ្នាដោយបញ្ច្រាសដំណោះស្រាយអារេឡេអាកូដ

លេខកូដ 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), ដោយសារតែយើងឆ្លងកាត់ធាតុទាំងអស់នៃអារេ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដោយសារតែយើងបានប្រើប្រេកង់ទំហំថេរឬរាប់អារេ។