c - O(n)在未排序数组中出现元素

标签 c arrays data-structures find-occurrences

这让我发疯:(

问题陈述:

输入一个未排序的数组,接着用户给出一个数字集合,程序应在该数组中打印给定数字的出现情况。

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

例:
输入数组:[1、1、1、2、2、0]

数字集合:

1个

2

1个

0

输出:

3

2

3

1个

约束:数组的大小可以为10 ^ 5,数字的集合的大小可以为10 ^ 5

附言:我用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);
        }

    }

    }

欢迎任何帮助:)

最佳答案

您可以简单地创建一个10 ^ 5的数组并将其初始化为0。现在遍历array并增加array中的值。就像遇到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]);
          }
    }
}

关于c - O(n)在未排序数组中出现元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45196515/

相关文章:

c - 如何将指针存储到二维数组中?

java - 这有可能在O(n)时间生成子数组吗?

database - 索引数据输入的备选项1

java - 阻塞队列 - 需要更多信息

ios - 如何通过Xcode 6为iOS构建C库?

c - 错误 : invalid use of vector register at operand 1

c - 通过函数传递字符串(C 编程)

javascript - 如何将多个数组组合成一个字符串?

c++ - 范围如何声明?

C、宏如何注册一个单元测试来执行?