उप-एर्रे लेटकोड समाधान उल्टाउँदै दुई एर्रे बराबर बनाउनुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ फेसबुक
एरे

समस्याले दुई एरेलाई समान बनाउँदछ सब-एरे लेटकोड समाधानलाई उल्टाउँदै हामीलाई दुई प्रदान गर्दछ एर्रेहरू। ती मध्ये एक लक्ष्य एरे हो र अर्को इनपुट एरे हो। इनपुट एरे प्रयोग गरेर, हामीले लक्ष्य एरे बनाउनु पर्छ। हामी इनपुट एर्रेमा कुनै पनि उप-एर्रे रिभर्स गर्न सक्छौं। तर हामी इनपुट एर्रेको एलिमेन्ट्स परिवर्तन गर्न सक्दैनौं। हेरफेर कसरी गर्ने भनेर हामीले कुनै तरिका खोज्न आवश्यक पर्दैन। यदि सम्भव भएमा गलत हो भने पनि फर्कनुहोस्। त्यसोभए, समाधानमा गहिरो डाइभ गर्नु अघि हामी केही उदाहरणहरू हेरौं।

उप-एर्रे लेटकोड समाधान उल्टाउँदै दुई एर्रे बराबर बनाउनुहोस्

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

स्पष्टीकरण: हामी पहिलो उप-एरे लाई सूची ० देखि २ सम्म उल्टाउन सक्दछौं, त्यसपछि हामी सब एरे १ देखि २ सम्म रिभर्स गर्दछौं। अन्त्यमा, हामी इन्डेक्स २ देखि 0. लाई रिवर्स गर्छौं र यसरी हामी लक्षित एरे बनाउन सक्छौं। । माथिको छवि हेरेर यसलाई अझ राम्रोसँग बुझ्न सकिन्छ।

उप-एर्रे लेटकोड समाधान उल्टाउँदै दुई एरे बराबर बनाउनको लागि दृष्टिकोण

समस्या गणनाको विधि प्रयोग गरेर सजीलै समाधान गर्न सकिन्छ। गणना गणना केहि मानक एल्गोरिदमहरू हुन्। यो गणना क्रममा साथै धेरै अन्य प्रश्नहरूमा प्रयोग गरीन्छ। त्यसैले यहाँ हामी लक्ष्य एरेबाट तत्वहरूको गणना राख्छौं। त्यसो भए हामी इनपुट एर्रेको एलिमेन्टहरू ट्रान्सभर्स गर्दछौं। जब हामी कुनै एलिमेन्ट भेट्छौं, हामी आवृत्ति वा गणना एरेबाट यसको गणना घट्छौं। यदि यो अपरेसनको बेलामा कुनै पनि सूचकांकले नकारात्मक मान राख्छ जुन हामी गलत फिर्ता गर्छौं।

फ्रिक्वेन्सी एरेमा नकारात्मक गणनाले इनपुट एर्रेमा एलिमेन्टको लागि ठूलो गणना देखाउँदछ। तर कसरी यसले समस्या समाधान गर्दछ? एकचोटि तपाईंलाई अवलोकन थाहा भएपछि जवाफ सरल छ। एकचोटि तपाईंले सब एर्रेको केहि उल्टो प्रदर्शन गर्न कोसिस गर्नुभयो। तपाईं सजिलैसँग पत्ता लगाउन सक्नुहुन्छ कि तपाईं जहाँ चाहानुहुन्छ कुनै पनि ठाउँमा आगत एर्रेको कुनै पनि तत्व राख्न सक्नुहुन्छ। त्यसोभए, यो नियम प्रयोग गरेर हामीले जाँच गर्नुपर्नेछ कि लक्षित एर्रेमा एन्टिमहरू इनपुट एरे जस्ता समान छन् कि छैनन्।

दुई एर्रे बराबर बनाउनको लागि कोड उप-एर्रे लेटकोड समाधान उल्टाउँदै

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 (१), किनकि हामीले स्थिर आकारको फ्रिक्वेन्सी वा एरे गणना गर्नुहोस्।