查找数组在小于O(n ^ 2)内重复的次数

Question

我写的示例代码.但这是n ^ 2

int a[]={1,4,1,5,2,2,4,3,4,1};
int b[][]=new int[5][2];
int i,j,k=0,count=1;
boolean temp=false;
for(i=0;i<a.length;i++)
{
    for(j=0;j<5;j++)
    {
        if(a[i]==b[j][0])
        {   temp=true;
            b[j][1]++;
            break;
        }
    }

    if(temp==false)
    {
        b[k][0]=a[i];
        b[k][1]=1;
        k++;    
    }
    temp=false;
}
for(i=0;i<5;i++)
{
    for(j=0;j<1;j++)
    {
    System.out.println(b[i][j]+" is repeated "+b[i][j+1]+" times");
    }
}

Answer 1

这是伪代码的解决方案:

Map<Int, Int> histogram;
for(number in array) {
    histogram[number]++;
}

现在histogram[somenumber]包含数字在数组中的次数 - O(n)假设Map查找项目O(1)

Answer 2

选项1:牺牲记忆速度.

• 使用像a这样的数据结构HashMap来记录每个数字的频率.
• 在O(n)时间内迭代以构建频率计数,然后迭代整个HashMap或提取一个值.

选项2:排序

• 排序,然后迭代整个排序结构或O(log n)以寻找特定值.
  • Quicksort具有平均n log n,O(n ^ 2)最坏情况,就地存储器.
  • Mergesort或heapsort是O(n log n)但在排序期间占用额外的内存