Frequency Leetcode Solution အားတိုး။ Array ကိုစီပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် ကို eBay Twilio
အခင်းအကျင်း HashMap sorting

ပြProbleနာဖော်ပြချက်

ကိန်းဂဏန်းမြောက်မြားစွာကိုပေးထားသောတန်ဖိုး၏ကြိမ်နှုန်းပေါ် မူတည်၍ တိုးမြှင့်နိုင်ရန်စီစဉ်ပါ။ တန်ဖိုးများစွာသည်တူညီသောကြိမ်နှုန်းရှိပါက၎င်းတို့ကိုအစဉ်လိုက်စီပါ။

နမူနာ

nums = [1,1,2,2,2,3]
[3,1,1,2,2,2]

ရှင်းလင်းချက်:

'3' မှာ 1 ကြိမ်နှုန်း၊ '1' မှာကြိမ်နှုန်း 2 နှင့် '2' မှာကြိမ်နှုန်း 3 ဖြစ်သည်။

nums = [2,3,1,3,2]
[1,3,3,2,2]

ရှင်းလင်းချက်:

'2' နှင့် '3' နှစ်ခုစလုံးတွင် 2 ကြိမ်နှုန်းရှိသည်၊ ထို့ကြောင့်၎င်းတို့ကိုအစဉ်လိုက်စီစဉ်ထားသည်။

ချဉ်းကပ်နည်း

ဤပြproblemနာတွင်ပထမတစ်ခုသည် element တစ်ခုစီ၏ကြိမ်နှုန်းကိုရေတွက်ရန်ဖြစ်သည်။ ဒီအတွက်ငါတို့ကသုံးနိုင်သည် hash မြေပုံ java သို့မဟုတ် c ++ တွင် unordered ထားရှိသည်။ ယခုကျွန်ုပ်တို့ရလဒ် array တွင်ကြိမ်နှုန်းမြင့်သောအရာများကိုပထမ ဦး ဆုံးပါ ၀ င်စေချင်သည်။
၎င်းအတွက်ကျွန်ုပ်တို့သည်မြေပုံတွင်သိမ်းထားပြီးဖြစ်သောစုစုပေါင်းကြိမ်နှုန်းကို အခြေခံ၍ ပေးထားသော input ခင်းကျင်းမှုကိုယခုခွဲနိုင်သည်။

အခုကျွန်တော်တို့ function အပြင်ဘက်ကိုနှိုင်းယှဉ်ကြည့်ရအောင်။ ဤတွင်ကျွန်ုပ်တို့သည် element (၂) ကိုနှိုင်းယှဉ်လေ့လာပြီး element တစ်ခုစီ၏ကြိမ်နှုန်းကိုကျွန်ုပ်တို့သိလိမ့်မည်။ အကယ်၍ a ၏ကြိမ်နှုန်းသည် b ထက်ကြီးလျှင်၊ b ကို array ထဲ၌ထည့်ပါ။ a နှင့် b ၏ကြိမ်နှုန်းတူညီလျှင်ထပ်မံတန်ဖိုးရှိသည့် element ကိုအရင်ထည့်ပါ။ ဥပမာ -

ဖြစ်ရပ်မှန် 1Frequency Leetcode Solution အားတိုး။ Array ကိုစီပါ

ဖြစ်ရပ်မှန် 2Frequency Leetcode Solution အားတိုး။ Array ကိုစီပါ

algorithm

  • hash မြေပုံတစ်ခုဖန်တီးပါ။
  • ကွင်းဆက်တစ်ခုဖွင့်ပြီး element တစ်ခုချင်းစီအတွက်ထို element ၏အရေအတွက်ကိုမြေပုံတွင်တိုးပါ။
  • ယခုမြေပုံတွင်ထည့်ထားသော၎င်း၏အရေအတွက်ကို သုံး၍ ကိန်းနှစ်ခုကိုနှိုင်းယှဉ်ခြင်းအတွက်နှိုင်းယှဉ်လုပ်ဆောင်ချက်တစ်ခုလုပ်ပါ။ ဒြပ်စင်နှစ်ခုနှိုင်းယှဉ်ပါနှင့်အထက်တွင်ဆွေးနွေးထားတဲ့အတိုင်းသူတို့ရဲ့အမိန့်ဆုံးဖြတ်ပါ။
  • ဒီနှိုင်းယှဉ်သုံးပြီးပေးထားသောခင်းကျင်း sort ။
  • အဆိုပါ Sorted ခင်းကျင်းပြန်သွားပါ။

အကောင်အထည်ဖော်ရေး

ကြိမ်နှုန်း Leetcode ဖြေရှင်းချက်တိုးမြှင့်ခြင်းဖြင့် Sort Array များအတွက် C ++ အစီအစဉ်

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

bool comp(pair<int,int> p1,pair<int,int> p2)
{
    if(p1.second == p2.second) return p1.first > p2.first;
    return p1.second < p2.second;
}

vector<int> frequencySort(vector<int>& nums) 
{
    unordered_map<int,int> m;
    for(auto x:nums) m[x]++;

    vector<pair<int,int> > v;

    for(auto p:m) v.push_back(p);

    sort(v.begin(),v.end(), comp);

    vector<int> res;
    for(auto p:v)
    {
        while(p.second--)
            res.push_back(p.first);
    }

    return res;        
}

int main() 
{
    vector<int> nums = {2,3,1,3,2};
    for(int x: frequencySort (nums))
        cout<<x<<" ";
    return 0; 
}
1 3 3 2 2

Frequency Leetcode Solution ကိုတိုးမြှင့်ခြင်းအားဖြင့် Sort Array အတွက် Java Program

import java.util.*;
import java.lang.*;

class Comp implements Comparator<Integer>{
    Map<Integer,Integer>map=Rextester.map;
    public int compare(Integer a,Integer b){
        if(map.get(a)>map.get(b))return 1;
        else if(map.get(b)>map.get(a))return -1;
        else{
            if(a>b)return -1;
            else if(a<b)return 1;
            return 0;
        }
    }
}
class Rextester
{  
    static Map<Integer,Integer>map;
    public static int[] frequencySort(int[] nums)
    {
        map=new HashMap<Integer,Integer>();
        for(int i:nums){
            if(map.containsKey(i)){
                map.put(i,1+map.get(i));
            }else{
                map.put(i,1);
            }
        }
        Integer[]arr=new Integer[nums.length];
        int k=0;
        for(int i:nums){
            arr[k++]=i;
        }
        Arrays.sort(arr,new Comp());
        k=0;
        for(int i:arr){
            nums[k++]=i;
        }
        return nums;
    }
    
    public static void main(String args[])
    {
        int[]nums={1,1,2,2,2,3};
        nums=frequencySort(nums);
        for(int i:nums)
        {
            System.out.print(i+" ");
        }
    }
}
1 3 3 2 2

ကြိမ်နှုန်း Leetcode ဖြေရှင်းချက်တိုးမြှင့်ခြင်းဖြင့် Sort Array များအတွက်ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာခြင်း

အချိန်ရှုပ်ထွေး

အို (nlog (n)) ဘယ်မှာ n သည် input ခင်းကျင်း၏အရွယ်အစားသည်။ hash မြေပုံအတွင်းထည့်သွင်းခြင်းနှင့်အသုံးပြုခြင်းသည် n (n) n element များအတွက်အချိန်နှင့် sorting သည် nlogn အချိန်ကြာသည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှု nlogn ဖြစ်လိမ့်မည်။

အာကာသရှုပ်ထွေးမှု 

အို ()) အဆိုးဆုံးမှာ array ထဲရှိကွဲပြားခြားနားသော element များဖြစ်နိုင်သည်။ ထို့ကြောင့်မြေပုံ၏အရွယ်အစားသည်အို (n) ဖြစ်လိမ့်မည်။