Sıralanmış massivdə baş verənlərin sayını hesablayın

Problem bəyanat

"Sıralanmış bir sıra içində meydana çıxma sayını hesabla" problemində bir sıra verdik serial. X-in bir tam olduğu X sıralanmış bir sıra içərisində baş vermə və ya tezlik sayını sayın.

misal

Input

13

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

3

Buraxılış

3

Sıralanmış massivdə baş vermiş sayların sayı üçün yanaşma 1

1. Sadəcə olaraq dəyişdirilmiş ikili axtarış aparın
2. X-in ilk meydana gəlməsini belə tapın:

1.  Dizinin orta elementinin X-ə bərabər olub olmadığını yoxlayın.
2. Bərabər və ya daha böyük element ortadadırsa, bölməni başlanğıcdan 1-ə qədər azaldır. İlk meydana gəlməni serialın ortasında sol tərəfdə edəcəyik.
3. Orta element daha kiçikdirsə, sıra sıralanarkən orta elementin sağ hissəsini yoxlayacağıq.
4. İlk hadisəni qaytarın.

3. İndi də oxşar olaraq X-də serialdakı son meydana gəlməni edərək tapın

1. Dizinin orta elementinin X-ə bərabər olub olmadığını yoxlayın
2. Bərabər və ya daha kiçik element ortadadırsa, bölməni ortadan + 1-ə qədər artırın. Sonuncu dəfə sıra ortasında sağ tərəfdə olacağımıza görə.
3. Dizinin sol tərəfində başqa axtarış
4. son hadisəni qaytarın

4. İndi baş vermə sayı sadəcə son hadisədir - ilk baş vermə + 1.

Həyata keçirilməsi

C ++ Proqramı

#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

Sıralanmış massivdə baş vermiş sayların sayı üçün yanaşma 2

1. Sadəcə alqoritm 1 ilə eyni yanaşma edin, ancaq upper_bound () və alt_bound funksiyalarından istifadə edin.
2. Upper_bound () funksiyalarından istifadə edərək son hadisəni və low_bound () funksiyaları vasitəsilə ilk baş verməni hesablayın.
3. Baş vermə sayı sadəcə upper_bound () - ilə əldə edilən indeksdir
4. alt_bound ().

Low_bound (), Upper_bound Standart Şablon Kitabxanası (STL) funksiyalarıdır.

Həyata keçirilməsi

C ++ Proqramı

#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

Sıralanmış massivdə baş vermiş sayların sayı üçün yanaşma 3

1. Sadəcə bir döngə işlədin.
2. X-ə bərabər bir element alsaq, sayını artırmağa başlayın
3. X-in sayını artırdığını görənə qədər X-dən fərqli bir rəqəm əldə edən kimi alınan sayını sıralanmış bir sıra kimi göstəririk.

Izahat

Bir dövrəni massivin əvvəlindən sonuna qədər aparın və x == a [i] nin sayını artırıb-artırmadığını yoxlayın. Budur bir nümunə götürək. a [] = {1, 2, 2, 2, 3, 4} və x = 2 olduqda x sayı 3-dür. Beləliklə, son cavabımız 3-dür.

Həyata keçirilməsi

C ++ Proqramı

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

Java Proqramı

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

Sıralanmış massivdə baş verən say sayına görə mürəkkəblik analizi

Zaman Mürəkkəbliyi - O (N) çünki bütün massivi gəzirik və x tezliyini sayırıq.
Kosmik Mürəkkəblik - O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

References