计算排序数组中的出现次数


难度级别 易得奖学金
经常问 Airbnb的 亚马逊 Apple 彭博 ByteDance Facebook Flipkart 谷歌 LinkedIn MakeMyTrip 微软 Netflix公司 神谕 讽刺 Twitter 尤伯杯 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. 如果等于或更大的元素位于中点,则将分区从start减小到mid-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;
}

Java程序

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是数组的大小。 在这里,我们使用二进制搜索,这导致我们的logN时间复杂度。
空间复杂度– O(1) 因为我们在这里不使用任何辅助空间。

方法2:对排序数组中的出现次数进行计数

  1. 只需执行与算法1相同的方法,只是使用upper_bound()和lower_bound函数。
  2. 使用upper_bound()计算最后一次出现,并通过Lower_bound()函数计算第一次出现。
  3. 出现次数只是由upper_bound()获得的索引–
  4. lower_bound()。

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是数组的大小。 在这里,我们使用具有logN时间复杂度的inbuild STL函数。
空间复杂度– 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;
}

Java程序

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) 因为我们在这里不使用任何辅助空间。

參考資料