დათარიღებული მასივის მოვლენების რაოდენობა


Რთული ტური Easy
ხშირად ეკითხებიან Airbnb Amazon Apple Bloomberg ByteDance Facebook Flipkart Google LinkedIn MakeMyTrip microsoft Netflix Oracle Quip Twitter Uber Yandex
Array ორობითი ძებნა

პრობლემის განცხადება

”დახარისხებული მასივის მოვლენების დათვლის რაოდენობის” პრობლემში ჩვენ მივაწოდეთ დახარისხებული მასივი დათვალეთ მოვლენების რაოდენობა ან სიხშირე 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.

განხორციელება

C ++ პროგრამა

#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 არის მასივის ზომა. აქ ვიყენებთ ორობით ძიებას, რომელიც მიგვიყვანს დროში სირთულისკენ.
კოსმოსური სირთულე - O (1) რადგან აქ არ ვხმარობთ რაიმე დამხმარე ადგილს.

დახარისხებული მასივის მოვლენების რაოდენობაზე მიდგომა 2

  1. უბრალოდ გააკეთეთ იგივე მიდგომა, როგორც 1 ალგორითმი, მაგრამ გამოიყენეთ upper_bound () და ქვედა_bound ფუნქციები.
  2. გამოთვალეთ ბოლო შემთხვევა upper_bound () და პირველი შემთხვევა lower_bound () ფუნქციების გამოყენებით.
  3. შემთხვევების რაოდენობა უბრალოდ ინდექსია, რომელიც მიღებულია upper_bound () - მიერ -
  4. ქვედა_ბმული ().

Low_bound (), Upper_bound სტანდარტული თარგი ბიბლიოთეკის (STL) ფუნქციებია.

განხორციელება

C ++ პროგრამა

#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 არის მასივის ზომა. აქ ვიყენებთ STL ფუნქციას, რომელსაც აქვს logN დროის სირთულე.
კოსმოსური სირთულე - O (1) რადგან აქ არ ვხმარობთ რაიმე დამხმარე ადგილს.

დახარისხებული მასივის მოვლენების რაოდენობაზე მიდგომა 3

  1. უბრალოდ აწარმოეთ მარყუჟი.
  2. თუ მივიღებთ X ტოლის ელემენტს დაიწყეთ რიცხვის გაზრდა
  3. სანამ დავინახავთ X- ს რაოდენობის გაზრდას და როგორც კი მივიღებთ X- სგან განსხვავებულ რიცხვს, ჩვენ ვაჩვენებთ მიღებულ რაოდენობას, რადგან ეს არის დახარისხებული მასივი.

განმარტება

გაუშვით ერთი ციკლი მასივის დასაწყისიდან ბოლომდე და შეამოწმეთ x == a [i] შემდეგ გაზარდეთ რაოდენობა. მოდით ავიღოთ მაგალითი. a [] = {1, 2, 2, 2, 3, 4} და x = 2, მაშინ x- ის რიცხვი არის 3. ასე რომ, ჩვენი საბოლოო პასუხია 3.

განხორციელება

C ++ პროგრამა

#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;
}

ჯავა პროგრამა

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

სირთულის ანალიზი დალაგებული მასივის მოვლენების რაოდენობის მიხედვით

დროის სირთულე - O (N) რადგან ჩვენ მთელ მასივს გადავკვეთთ და ვთვლით x სიხშირეს.
კოსმოსური სირთულე - O (1) რადგან აქ არ ვხმარობთ რაიმე დამხმარე ადგილს.

ლიტერატურა