未排序数组中某个元素的出现时间复杂度为 O(n)

Question

这让我抓狂:(

问题陈述：

未排序的数组是 inputed.Next 用户给出一组数字，程序应打印给定数字在该数组中的出现。

这应该运行时间复杂度为 O(n)。

示例：输入数组：[1, 1, 1, 2, 2, 0]

号码集合：

1

2

1

0

输出：

3

2

3

1

约束：数组的大小可以是 10^5，数字集合的大小可以是 10^5

P.S:我用 O(n^2)

做了一个代码

#include<stdio.h>
#include<stdlib.h>
void main(){
    int *n,size,key,count=0;
    scanf("%d",&size);
    n=(int*)malloc(size*sizeof(int));
    for(int i=0;i<size;i++){
        scanf("%d",&n[i]);
    }
    scanf("%d",&key);
    for(int i=0;i<key;i++){
        count=0;
        int temp=0;
        scanf("%d",&temp);
        for(int j=0;j<size;j++){
            if(temp==n[j])
                 count+=1;
        }
        printf("\n");
        if(count==0){
            printf("NOT PRESENT");
        }
        else{
            printf("%d",count);
        }

    }

    }

欢迎任何帮助:)

Answer 1

元素范围小。因此，为可能的值创建一个计数器数组，并为找到的每个值递增计数。例如，如果找到 2，则递增 counter[2].

然后给定您的数字集合，只需进行数组查找即可获得计数。

Answer 2

一个非常简单的方法是让结果数组的键位于值所在的位置。

我的 C 技能有点弱，但是在伪 C 中是这样的（你必须调整它才能使其正常工作：

int size = 10*10*10*10*10;
int[size] input = getInput();
int[size] results = new int[size](0); // fill array with zeros

for(int i = 0; i < size; i++) {
  if (input[i] === -1)
    break; // assuming -1 signifies the end of the input

  output[input[i]]++; // increment the value at the index that matches the number by one
}

for(int i = 0; i < size; i++) {
  if (output[i] === 0)
    continue; // number wasn't in array

  printf('%d', output[i]);
}

基本上，您将数组的输入放在输出的匹配索引中。

因此，如果您的输入是 5,3,2,1,1,5,3,2,1，您将输入输出：

output[5]++;
output[3]++;
output[2]++;
output[1]++;
output[1]++;
output[5]++;
output[3]++;
output[2]++;
output[1]++;

生成如下所示的数组：

[0, 3, 2, 2, 0, 1]

然后你就输出它，跳过零，因为它们不存在。

Answer 3

时间复杂度为O(max(m,n))，其中m是数组的大小，n是集合的大小。所需的 space 是 O(p)，其中 p 是数组中可能出现的整数范围。我们将使用 p0 表示该范围的下限。

解决方法很简单：

构造一个大小为 p 的数组 C 并将所有值设置为零
遍历输入数组并为每个值 k - 将 C[k-p0] 增加 1。现在您有每个值的计数。
遍历集合并为每个值 k - 打印 C[k-p0]

Answer 4

您可以简单地创建一个 10^5 的数组并用 0 初始化它。现在遍历数组并增加数组中的值。就像你遇到一个 5 增量 arr[5] 现在你可以在 O(1) 时间内回答查询。

下面是java中的一段代码。

import java.util.Scanner;
public class test
{
    public static void main(String args[])
    {
          Scanner in=new Scanner(System.in());
          int n=s.nextInt();
          int arr[]=new int[100001];       //Array is initialized 0 
          for(int i=0;i<n;i++)
          {
               int num=s.nextInt();
               arr[num]++;
          }
          while(s.hasnextInt())
          {
              int p=s.nextInt();
              System.out.println(arr[p]);
          }
    }
}

未排序数组中某个元素的出现时间复杂度为 O(n)

Occurence of a element in unsorted array by O(n)

c

arrays

data-structures

find-occurrences