በአንድ ድርድር ሌቲኮድ መፍትሔ ውስጥ ዕድለኛ ኢንተግሪን ይፈልጉ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Microsoft
ሰልፍ

የችግር እሴት

በችግሩ ውስጥ “በአንድ ረድፍ ውስጥ ዕድለኛ ውህደትን ይፈልጉ” እኛ ተሰጠናል ደርድር በድርድሩ ውስጥ ያለው ድግግሞሽ ከእሴቱ ጋር እኩል ከሆነ ኢንቲጀር ዕድለኛ ተብሎ የሚጠራበት።

የእኛ ተግባር ትልቁን ዕድለኛ ቁጥር መመለስ ነው ፡፡ እንደዚህ ያለ ቁጥር ከሌለ መመለስ አለብን -1. በድርድሩ ውስጥ ያሉት እሴቶች ከ 1 እስከ 500 መካከል ያሉ ሲሆን የአደራጁ ርዝመት ቢበዛ 500 ነው ፡፡

ለምሳሌ

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

ማስረጃ:

በአንድ ድርድር ሌቲኮድ መፍትሔ ውስጥ ዕድለኛ ኢንተግሪን ይፈልጉ

የ 2 ድግግሞሽ 2 እና የ 3 እና የአራት ድግግሞሽ 1. እንደ 2 ብቸኛ ዕድለኛ ቁጥር ነው ስለሆነም መልሳችን ይህ ነው ፡፡

በድርድር ሌቲኮድ መፍትሄ ውስጥ ዕድለኛ ውህደትን ለማግኘት የመደርደር አቀራረብ

የእያንዳንዱን ቁጥር ክስተቶች ብዛት ለመቁጠር እና ከዚያ የተሰጠውን ሁኔታ የሚያረካ ትልቁን ንጥረ ነገር ለማግኘት እንደፈለግን ፡፡ ይህንን ለማድረግ አንድ ቁጥር እንመርጣለን እና ከዚያ በኋላ ሁሉንም ክስተቶች ለመቁጠር መላውን ረድፍ እናቋርጣለን እና ሁኔታውን የሚያረካ ትልቁን ንጥረ ነገር እንመርጣለን ፡፡ እዚህ የተሟላ ድርድር n ጊዜዎችን ማለፍ ያስፈልገናል ስለሆነም የጊዜ ውስብስብነቱ O (n * n) ይሆናል ፡፡ ድርድርን በመደርደር አፈፃፀሙን ከፍ ማድረግ እንችላለን። ይህ ተመሳሳይ ቁጥሮችን አንድ ላይ ያመጣል። እኛ የሚከተሉትን እርምጃዎች እንከተላለን

  1. ድርድሩን በሚቀንሰው ቅደም ተከተል ለይ።
  2. ሁኔታውን የሚያሟላ ከሆነ ያጋጠመው ንጥረ ነገር ሁሉንም ክስተቶች ይቁጠሩ እና ከዚያ ይመልሱ።
  3.  በመጨረሻ ፣ ምንም ንጥረ ነገር ሁኔታውን ካላሟላ ከዚያ ይመለሱ -1.

አፈጻጸም

በአንድ ድርድር ውስጥ ዕድለ-ቢስ አመላካች ለማግኘት የ C ++ ኮድ

#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.

አፈጻጸም

በአንድ ድርድር ውስጥ ዕድለ-ቢስ አመላካች ለማግኘት የ C ++ ኮድ

#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) ምክንያቱም እኛ የሃሽ ጠረጴዛ እየፈጠርን ነው ፡፡

ማጣቀሻዎች