අරා ලීට්කෝඩ් විසඳුමක වාසනාවන්ත පූර්ණ සංඛ්‍යාවක් සොයා ගන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ මයික්රොසොෆ්ට්
අරා

පටුන

ගැටළු ප්රකාශය

“අරාවකින් වාසනාවන්ත පූර්ණ සංඛ්‍යාවක් සොයා ගන්න” යන ගැටලුවේදී අපට ලබා දී ඇත්තේ අ අරාව අරාවෙහි සංඛ්‍යාතය එහි අගයට සමාන නම් පූර්ණ සංඛ්‍යාවක් වාසනාවන්ත ලෙස හැඳින්වේ.

අපගේ කාර්යය වන්නේ විශාලතම වාසනාවන්ත අංකය ආපසු ලබා දීමයි. එවැනි අංකයක් නොමැති නම් -1 නැවත ලබා දිය යුතුය. අරාවෙහි අගයන් 1 ත් 500 ත් අතර වන අතර අරාවෙහි දිග උපරිම 500 කි.

උදාහරණයක්

arr = [2,2,3,4]
2

පැහැදිලි කිරීම:

අරා ලීට්කෝඩ් විසඳුමක වාසනාවන්ත පූර්ණ සංඛ්‍යාවක් සොයා ගන්න

2 හි සංඛ්‍යාතය 2 වන අතර 3 සහ හතරේ සංඛ්‍යාතය 1 වේ. 2 එකම වාසනාවන්ත නිඛිලය බැවින් මෙය අපගේ පිළිතුරයි.

අරා ලීට්කෝඩ් විසඳුමක වාසනාවන්ත පූර්ණ සංඛ්‍යාවක් සොයා ගැනීම සඳහා ප්‍රවේශය වර්ග කිරීම

එක් එක් සංඛ්‍යාවේ සිදුවීම් ගණන ගණනය කිරීමට අපට අවශ්‍ය බැවින්, දී ඇති කොන්දේසිය තෘප්තිමත් කරන විශාලතම අංගය සොයා ගන්න. මෙය සිදු කිරීම සඳහා අපි අංකයක් තෝරාගෙන එහි සිදුවීම් ගණනය කිරීම සඳහා මුළු අරාව හරහා ගමන් කර තත්වය තෘප්තිමත් කරන විශාලතම අංගය තෝරා ගනිමු. මෙහිදී අපට සම්පූර්ණ අරාව n වාරයක් ගමන් කළ යුතුය, එවිට කාල සංකීර්ණතාව O (n * n) බවට පත්වේ. අරාව වර්ග කිරීමෙන් අපට කාර්ය සාධනය වැඩි කළ හැකිය. මෙය එකම සංඛ්‍යා එකට ගෙන එනු ඇත. අපි මෙම පියවර අනුගමනය කරන්නෙමු:

  1. අඩු වන අනුපිළිවෙලින් අරාව වර්ග කරන්න.
  2. හමු වූ මූලද්‍රව්‍යයේ තත්වය තෘප්තිමත් නම් එය නැවත ලබා දෙන්න.
  3.  අවසානයේදී, කිසිදු මූලද්‍රව්‍යයක් තත්වය තෘප්තිමත් නොකරන්නේ නම් -1 නැවත ලබා දෙන්න.

ක්රියාත්මක කිරීම

අරාවකින් ලකී ඉන්ටීරියර් සොයා ගැනීම සඳහා සී ++ කේතය

#include <bits/stdc++.h> 
using namespace std; 
int findLucky(vector<int>& arr) {
    sort(begin(arr), end(arr), greater<int>());
    int cnt = 1;
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] == arr[i - 1])
            ++cnt;
        else {
            if (arr[i - 1] == cnt)
                return cnt;
            cnt = 1;
        }
    }
    return arr.back() == cnt ? cnt : - 1;
}

int main() 
{ 
vector<int> arr = {2,2,3,4}; 
 int ans=findLucky(arr);
 cout<<ans<<endl;
 return 0;
}
2

අරාව තුළ ලකී ඉන්ටර්ජර් සොයා ගැනීම සඳහා ජාවා කේතය

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
public static int findLucky(int[] arr) {
    Arrays.sort(arr);
    int ans = 0;
    for (int i = arr.length - 1; i >= 0; i--) {
        ans++;
        if (i == 0 || arr[i] != arr[i - 1]) {
            if (ans == arr[i]) {
                return ans;
            }
            ans = 0;
        }
    }
    return -1;
}
  public static void main(String[] args) {
        int [] arr = {2,2,3,4}; 
        int ans=findLucky(arr); 
        System.out.println(ans);
  }
}
2

අරා ලීට්කෝඩ් විසඳුමක වාසනාවන්ත පූර්ණ සංඛ්‍යාවක් සොයා ගැනීමේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඉහත කේතයේ කාල සංකීර්ණතාව වේ ඕ (nlogn) මොකද අපි දී ඇති අරාව වර්ග කරනවා. මෙහි n යනු දී ඇති අරාවේ දිග වේ.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ ඕ (1) මොකද අපි උත්තරය ගබඩා කරන්න විචල්‍යයක් විතරයි පාවිච්චි කරන්නේ.

අරා ලීට්කෝඩ් විසඳුමක වාසනාවන්ත පූර්ණ සංඛ්‍යාවක් සොයා ගැනීම සඳහා ප්‍රවේශය

හැෂිං ආධාරයෙන් වර්ග කිරීමකින් තොරව එක් එක් අංකයේ සිදුවීම් එකවර එකවර ගණනය කළ හැකිය. අපි මෙම පියවර අනුගමනය කරන්නෙමු:

  1. මූලද්‍රව්‍යයේ අගය උපරිම 501 ක් විය හැකි බැවින් 500 ප්‍රමාණයේ සංඛ්‍යාත අරාවක් සාදන්න.
  2. දී ඇති අරාව සම්පුර්ණයෙන්ම ගමන් කර සංඛ්‍යාත අරාවෙහි එක් එක් මූලද්‍රව්‍යයන්ගේ ගණන ගබඩා කරන්න.
  3. දැන් සංඛ්‍යාත අරාව අවසානයේ සිට ගමන් කරන්න. කිසියම් මූලද්‍රව්‍යයක් තත්වය තෘප්තිමත් කරන්නේ නම් එය ආපසු ලබා දෙන්න.
  4.  අවසානයේදී, කිසිදු මූලද්‍රව්‍යයක් තත්වය තෘප්තිමත් නොකරන්නේ නම් -1 නැවත ලබා දෙන්න.

ක්රියාත්මක කිරීම

අරාවකින් ලකී ඉන්ටීරියර් සොයා ගැනීම සඳහා සී ++ කේතය

#include <bits/stdc++.h> 
using namespace std; 
int findLucky(vector<int>& arr) {
    int m[501] = {};
    for (auto n : arr)
        ++m[n];
    for (auto n = arr.size(); n > 0; --n)
        if (n == m[n])
            return n;
    return -1;
}

int main() 
{ 
vector<int> arr = {2,2,3,4}; 
 int ans=findLucky(arr);
 cout<<ans<<endl;
 return 0;
}
2

අරාව තුළ ලකී ඉන්ටර්ජර් සොයා ගැනීම සඳහා ජාවා කේතය

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int findLucky(int[] arr) {
    int[] m = new int[501];
    for(int i=0;i<arr.length;i++)
        ++m[arr[i]];
    for (int n = arr.length; n > 0; --n)
        if (n == m[n])
            return n;
    return -1;
    }
  public static void main(String[] args) {
        int [] arr = {2,2,3,4}; 
        int ans=findLucky(arr); 
        System.out.println(ans);
  }
}
2

අරා ලීට්කෝඩ් විසඳුමක වාසනාවන්ත පූර්ණ සංඛ්‍යාවක් සොයා ගැනීමේ සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඉහත කේතයේ කාල සංකීර්ණතාව වේ සාමාන්ය (n) මොකද අපි දී ඇති අරාව හරහා ගමන් කරන්නේ එක් වරක් පමණි. මෙහි n යනු දී ඇති අරාවේ දිග වේ.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ සාමාන්ය (n) මොකද අපි හැෂ් මේසයක් නිර්මාණය කරනවා.

ආශ්රිත