වර්ග කළ අරාවක සිදුවීම් ගණන ගණනය කරන්න  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ Airbnb ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance ෆේස්බුක් ෆ්ලිප්කාර්ට් ගූගල් LinkedIn MakeMyTrip මයික්රොසොෆ්ට් Netflix ඔරකල් ඉක්මන් කරන්න ට්විටර් Uber Yandex
අරා ද්විමය සෙවීම

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

“වර්ග කළ අරා හි සිදුවීම් ගණන” ගැටලුවේදී, අපි වර්ග කර ඇත අරාව. X හි පූර්ණ සංඛ්‍යාවක් වන X හි වර්ග කළ අරාවක සිදුවීම් හෝ සංඛ්‍යාත ගණන ගණනය කරන්න.

උදාහරණයක්  

ආදාන

13

1 2 2 2 2 3 3 3 4 4 4 5 5

3

ප්රතිදාන

3

වර්ග කළ අරාවක සිදුවීම් ගණන සඳහා 1 ප්‍රවේශය  

1. නවීකරණය කරන ලද ද්විමය සෙවුමක් කරන්න
2. X හි පළමු සිදුවීම මේ ආකාරයෙන් සොයා ගන්න:

  1.  අරාවේ මැද අංගය X ට සමාන දැයි පරීක්ෂා කරන්න.
  2. සමාන හෝ වැඩි මූලද්‍රව්‍යයක් මැද නම්, කොටස ආරම්භයේ සිට 1 මැද දක්වා අඩු කරන්න. අරාව මැද වම් පැත්තේ පළමු සිදුවීම අපට ඇති බැවින්.
  3. මැද මූලද්‍රව්‍යය කුඩා නම් අරාව වර්ග කර ඇති බැවින් අපි මැද මූලද්‍රව්‍යයේ දකුණු පැත්තේ පරීක්ෂා කරන්නෙමු.
  4. පළමු සිදුවීම නැවත ලබා දෙන්න.

3. දැන් ඒ හා සමානව අරාවෙහි X හි අවසාන සිදුවීම සොයා ගන්න

  1. අරාවේ මැද අංගය X ට සමාන දැයි පරීක්ෂා කරන්න
  2. සමාන හෝ කුඩා මූලද්‍රව්‍යය මැද නම්, කොටස මැද + 1 සිට ඉහළට වැඩි කරන්න. අරාව මැද දකුණු පසින් අපට අවසාන සිදුවීම සිදුවනු ඇත.
  3. අරාවෙහි වම් පැත්තේ සෙවීම
  4. අවසාන සිදුවීම නැවත ලබා දෙන්න
මෙයද බලන්න
ඕනෑම මූලද්රව්ය දෙකක් අතර අවම වෙනසක් සොයා ගන්න

4. දැන් සිදුවීම් ගණන හුදෙක් අවසාන සිදුවීමයි - පළමු සිදුවීම + 1.

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

සී ++ වැඩසටහන

#include <bits/stdc++.h>
using namespace std;
int first_occurence(int arr[],int N,int X)
{
  int low = 0 , high = N-1;
  int first = INT_MAX;
  while(low <= high)
  {
    int mid = low + ((high-low)>>1);
    if(arr[mid] == X) //if found then check the left part for further occurence
    {
      if(mid < first)
      first = mid;
      high = mid-1;
    }
    else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
      low = mid + 1;
    else if (arr[mid] > X)//if middle element is larger than X check in left subpart
      high = mid - 1;
  }
  
  return first;
}
int last_occurence(int arr[],int N,int X)
{
  int low = 0 , high = N-1;
  int last = INT_MIN;
  
  while(low <= high)
  {
    int mid = low + ((high-low)>>1);
    if(arr[mid] == X) //if found check in right subpart for last occurence
    {
      if(mid > last)
      last = mid;
      low = mid+1;
    }
    else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
      low = mid + 1;
    else if (arr[mid] > X)//if middle element is larger than X check in left subpart
      high = mid - 1;
  }
  
  return last;
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
  int X; // number whose count is to be found out
  cin >> X;
  int count = 0; //initially its count is zero
  int last = last_occurence(a,n,X);
  if(last != INT_MIN)
    count += last;
  
  int first = first_occurence(a,n,X);
  if(first != INT_MAX)
    count -= first;
  cout<<last-first+1<<endl;  
  return 0;
}

ජාවා වැඩසටහන

import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static int first_occurence(int arr[],int N,int X)
    {
      int low = 0 , high = N-1;
      int first = 10000000;
      while(low <= high)
      {
        int mid = low + ((high-low)>>1);
        if(arr[mid] == X) //if found then check the left part for further occurence
        {
          if(mid < first)
          first = mid;
          high = mid-1;
        }
        else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
          low = mid + 1;
        else if (arr[mid] > X)//if middle element is larger than X check in left subpart
          high = mid - 1;
      }
      return first;
    }
    public static int last_occurence(int arr[],int N,int X)
    {
      int low = 0 , high = N-1;
      int last = -1;
      while(low <= high)
      {
        int mid = low + ((high-low)>>1);
        if(arr[mid] == X) //if found check in right subpart for last occurence
        {
          if(mid > last)
          last = mid;
          low = mid+1;
        }
        else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
          low = mid + 1;
        else if (arr[mid] > X)//if middle element is larger than X check in left subpart
          high = mid - 1;
      }
      return last;
    }
    public static int abs(int x)
    {
        if(x<0)
            x=x*-1;
        return x;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int X = sr.nextInt(); // number whose count is to be found out
        int count = 0; //initially its count is zero
        int last = last_occurence(arr,n,X);
        if(last != -1)
          count += last;
        int first = first_occurence(arr,n,X);
        if(first != 10000000)
          count -= first;
        System.out.println(last-first+1);
    }
}
8
1 1 2 2 2 3 4 5 
2
3

වර්ග කළ අරා වල සිදුවීම් ගණන ගණනය කිරීම සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණතාව - O (logN) මෙහි N යනු අරාවෙහි විශාලත්වයයි. මෙහිදී අපි ද්විමය සෙවුමක් භාවිතා කරන අතර එමඟින් ලොග්එන් කාල සංකීර්ණතාවයට අපව යොමු කරයි.
අභ්‍යවකාශ සංකීර්ණතාව - ඕ (1) අපි මෙහි කිසිදු සහායක ඉඩක් භාවිතා නොකරන නිසා.

මෙයද බලන්න
ප්‍රමාණයේ සෑම කවුළුවකම පැහැදිලි මූලද්‍රව්‍ය ගණනය කරන්න

වර්ග කළ අරාවක සිදුවීම් ගණන සඳහා 2 ප්‍රවේශය  

  1. ඇල්ගොරිතම 1 ට සමාන ප්‍රවේශයක් කරන්න, නමුත් ඉහළ_බවුන්ඩ් () සහ පහළ_බවුන්ඩ් ශ්‍රිත භාවිතා කරන්න.
  2. ඉහළ_බවුන්ඩ් () භාවිතා කරමින් අවසාන සිදුවීම සහ පහළ_බවුන්ඩ් () ශ්‍රිත හරහා පළමු සිදුවීම ගණනය කරන්න.
  3. සිදුවීම් ගණන හුදෙක් ඉහළ_බවුන්ඩ් () මගින් ලබාගත් දර්ශකයයි -
  4. low_bound ().

Low_bound (), ඉහළ_බ ound ් යනු සම්මත ආකෘති පුස්තකාල (STL) කාර්යයන් වේ.

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

සී ++ වැඩසටහන

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int X; // number whose count is to be found out
    cin >> X;
    int count = 0; //initially its count is zero
    count  = upper_bound(a,a+n,X) - lower_bound(a,a+n,X); 
    cout<<count;
    return 0;
}
8
1 1 2 2 2 3 4 5 
4
1

වර්ග කළ අරා වල සිදුවීම් ගණන ගණනය කිරීම සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණතාව - O (logN) මෙහි N යනු අරාවෙහි විශාලත්වයයි. මෙහිදී අපි භාවිතා කරන්නේ ලොග්එන් කාල සංකීර්ණතාවයෙන් යුත් ඉන්බිල්ඩ් එස්.ටී.එල්.
අභ්‍යවකාශ සංකීර්ණතාව - ඕ (1) අපි මෙහි කිසිදු සහායක ඉඩක් භාවිතා නොකරන නිසා.

වර්ග කළ අරාවක සිදුවීම් ගණන සඳහා 3 ප්‍රවේශය  

  1. හුදෙක් ලූපයක් ධාවනය කරන්න.
  2. අපට X ට සමාන මූලද්‍රව්‍යයක් ලැබුනහොත් ගණන වැඩි කිරීම ආරම්භ කරන්න
  3. X ගණනය කිරීම වැඩි කරන තෙක් අපට X ට වඩා වෙනස් සංඛ්‍යාවක් ලැබුණු විගසම අපි ලබාගත් අගය පෙන්වන්නේ එය වර්ග කළ අරාවකි.

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

අරාවේ ආරම්භයේ සිට අවසානය දක්වා එක් ලූපයක් ධාවනය කර x == a [i] තිබේදැයි පරීක්ෂා කර ගණනය වැඩි කරන්න. මෙන්න අපි උදාහරණයක් ගනිමු. a [] = {1, 2, 2, 2, 3, 4} සහ x = 2 එවිට x ගණන 3 වේ. එබැවින් අපගේ අවසාන පිළිතුර 3 වේ.

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

සී ++ වැඩසටහන

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int X; // number whose count is to be found out
    cin >> X;
    int count = 0; //initially its count is zero
    for(int i=0;i<n;i++)
    if(a[i]==X)
      count++;
    cout<<count;
    return 0;
}

මෙයද බලන්න
රේඛීය වේලාවේ 3 ප්‍රමාණයේ අනුපිළිවෙලක් සොයා ගන්න

ජාවා වැඩසටහන

import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int X = sr.nextInt(); // number whose count is to be found out
        int count = 0; //initially its count is zero
        for(int i=0;i<n;i++)
        if(arr[i]==X)
          count++;
        System.out.println(count);
    }
}
8
1 1 2 2 2 3 4 5 
1
2

වර්ග කළ අරා වල සිදුවීම් ගණන ගණනය කිරීම සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණතාව - ඕ (එන්) මොකද අපි මුළු අරාව හරහා ගමන් කර x සංඛ්‍යාතය ගණනය කරමු.
අභ්‍යවකාශ සංකීර්ණතාව - ඕ (1) අපි මෙහි කිසිදු සහායක ඉඩක් භාවිතා නොකරන නිසා.

ආශ්රිත