स्ट्रॅट्सची तुलना सर्वात लहान कॅरेक्टर लेटकोड सोल्यूशनच्या फ्रीक्वेंसीनुसार करा


अडचण पातळी सोपे
वारंवार विचारले Google ओरॅकल
अरे अक्षरमाळा

स्ट्रिंग्जची वारंवारता सर्वात लहान कॅरेक्टर लीटकोड सोल्यूशनच्या वारंवारतेनुसार तुलना करते, आम्ही असे म्हणतो की, रिकामे नसलेल्या जागी आपण फ (फ) चे कार्य परिभाषित करतो. स्ट्रिंग चे जसे की फॅ (एस) स्ट्रिंगमधील सर्वात लहान वर्णांच्या वारंवारतेइतके असतात. मग आम्हाला काही शब्द आणि काही प्रश्न दिले जातात. प्रत्येक क्वेरीसाठी आम्हाला f (शब्द)> f (क्वेरी_शब्द) अशा शब्दांची संख्या शोधणे आवश्यक आहे. मग आम्हाला सर्व शंकांचे उत्तर वेक्टर किंवा अ‍ॅरे म्हणून परत करावे लागेल. तर, समाधानात खोल जाण्यापूर्वी काही उदाहरणे पाहूया.

queries = ["cbd"], words = ["zaaaz"]
[1]

स्पष्टीकरणः f (“zaaaz”) =,, कारण सर्वात लहान वर्ण 'a' आहे ज्याची वारंवारता to च्या समान आहे, तर f (“cbd”) = १. तर आपल्याकडे फक्त एकच शब्द आहे जो f (i) आहे )> फ (क्वेरी_शब्द).

स्ट्रॅट्सची तुलना सर्वात लहान कॅरेक्टर लेटकोड सोल्यूशनच्या फ्रीक्वेंसीनुसार करा

queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
[1,2]

स्पष्टीकरणः म्हणून दिलेल्या सर्व शब्दांसाठी परिभाषित फंक्शनच्या मूल्याची गणना केल्यानंतर. आपल्याला f (“a”) = 1, f (“aa”) = 2, f (“aaa”) = 3, f (“aaa”) = 4 ”मध्ये दिलेल्या शब्दांच्या फंक्शनचे मूल्य मूल्यांकन केल्यावर मिळेल. क्वेरीज, आपल्याला f (“bbb”) = 3, f (“cc”) = २ ”आढळले आहेत. तर आपण f (“ bbb ”) या शब्दासाठी“ aaa ”या शब्दासाठी फंक्शन मूल्य आहे. 2. पेक्षा जास्त. त्याचप्रमाणे, “cc” या शब्दासाठी आपल्याकडे “aaa”, “aaa” असे शब्द आहेत ज्याचे फंक्शन व्हॅल्यू जास्त आहे.

सर्वात लहान पातळ्यांच्या लेटकोड सोल्यूशनच्या वारंवारतेनुसार स्ट्रिंग्सची तुलना करण्याचा दृष्टीकोन

स्ट्रिंग्जची वारंवारता सर्वात लहान कॅरेक्टर लेटकोड सोल्यूशनच्या स्ट्रिकची तुलना करा क्वेरी शब्दांच्या फंक्शनच्या मूल्यापेक्षा जास्त असलेल्या परिभाषित फंक्शनसाठी मूल्य असलेल्या इनपुटमधून शब्दांची संख्या शोधण्यास सांगितले जाते. रिकामे नसलेल्या तारांवर परिभाषित केलेले कार्य फ (एस) स्ट्रिंगमधील सर्वात लहान वर्णांच्या वारंवारतेइतके असते. प्रथम आपण सर्व क्वेरी शब्दांसाठी फंक्शनचे मूल्य शोधू. आम्ही सर्व इनपुट शब्दांसाठी तेच करतो. आम्ही एक अतिरिक्त अ‍ॅरे देखील तयार करतो जी i च्या फंक्शन व्हॅल्यू असलेल्या शब्दाची संख्या संग्रहित करते. हा अ‍ॅरे आम्हाला निरंतर वेळेत चौकशीसाठी उत्तरे शोधण्यात मदत करेल. अ‍ॅरेचा प्रत्येक निर्देशांक i शब्दांची संख्या संदर्भित करतो ज्यात फंक्शन मूल्य = i.

फंक्शन व्हॅल्यूचे मूल्यांकन करून आमच्या अस्थायी अ‍ॅरेमध्ये संचयित केल्यानंतर. आम्ही तात्पुरते अ‍ॅरेचा प्रत्यय मिळवितो की प्रत्येक अनुक्रमणिका आता फंक्शन मूल्य i किंवा त्या समान असलेल्या एकूण शब्दांची संख्या संचयित करते. आता आम्ही प्रत्येक क्वेरी शब्दाचे उत्तर फक्त अ‍ॅरे किंवा वेक्टरमध्ये संचयित करतो आणि ते परत करतो.

सर्वात लहान अक्षर लेटकोड सोल्यूशनच्या वारंवारतेनुसार स्ट्रिंग्जची तुलना करण्यासाठी कोड

सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
    vector<int> q;
    for(auto x: queries){
        int f[26] = {0};
        int mn = 26;
        for(auto y: x){
            f[y-'a']++;
            mn = min(mn, y-'a');
        }
        q.push_back(f[mn]);
    }

    int fr[12];memset(fr, 0, sizeof fr);
    for(auto x: words){
        int f[26] = {0};
        int mn = 26;
        for(auto y: x){
            f[y-'a']++;
            mn = min(mn, y-'a');
        }
        fr[f[mn]]++;
    }
    for(int i=9;i>=0;i--)
        fr[i] += fr[i+1];
    vector<int> ans;
    for(auto x: q){
        ans.push_back(fr[x+1]);
    }
    return ans;
}

int main(){
    vector<string> queries = {"bbb","cc"};
    vector<string> words = {"a","aa","aaa","aaaa"};

    vector<int> answer = numSmallerByFrequency(queries, words);
    for(auto x: answer)
        cout<<x<<" ";
}
1 2

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        ArrayList<Integer> q = new ArrayList<Integer>();
        for(String x: queries){
            int[] f = new int[26];
            for(int i=0;i<26;i++)
                f[i] = 0;
            int mn = 26;
            int sz = x.length();
            for(int i=0;i<sz;i++){
                int y = x.charAt(i);
                f[y-'a']++;
                mn = Math.min(mn, y-'a');
            }
            q.add(f[mn]);
        }
 
        int[] fr = new int[12];
        for(int i=0;i<12;i++)
            fr[i] = 0;
        for(String x: words){
            int[] f = new int[26];
            for(int i=0;i<26;i++)
                f[i] = 0;
            int mn = 26;
            int sz = x.length();
            for(int i=0;i<sz;i++){
                int y = x.charAt(i);
                f[y-'a']++;
                mn = Math.min(mn, y-'a');
            }
            fr[f[mn]]++;
        }
        for(int i=9;i>=0;i--)
            fr[i] += fr[i+1];
        int[] ans = new int[queries.length];
        for(int i=0;i<q.size();i++){
            ans[i] = (fr[q.get(i)+1]);
        }
        return ans;
    }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    String[] queries = {"bbb","cc"};
      String[] words = {"a","aa","aaa","aaaa"};
 
      int[] answer = numSmallerByFrequency(queries, words);
      for(int x: answer)
          System.out.print(x+" ");
  }
}
1 2

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (Q + N), कारण आपल्याला सर्व शब्दांसाठी फंक्शन व्हॅल्यू मोजायचे आहे आणि शब्दांची लांबी 10 पेक्षा कमी किंवा समान आहे. अशा प्रकारे वेळ जटिलता रेषात्मक आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (प्र), आम्ही तात्पुरते वापरासाठी उत्तर संचयित करण्यासाठी अ‍ॅरे आणि आकार 10 चे अतिरिक्त अ‍ॅरे तयार केल्यामुळे. जागेची जटिलता देखील रेषात्मक आहे.