在小于 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] 包含该数字在数组中的次数 - 假设 Map 在 O(n) 中code> 在 O(1) 中查找项目

Answer 2

选项 1：牺牲内存以换取速度。

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

选项 2：排序

• 排序，然后迭代整个排序结构或 O(log n) 来查找特定值。
  • 快速排序的平均数为 n log n，最坏情况为 O(n^2)，适合内存。
  • 合并排序或堆排序的时间复杂度为 O(n log n)，但在排序过程中会占用额外的内存

Answer 3

伪代码：

counts = dictionary default to 0

for each element in list:
    counts[element]+=1

O(n)

Answer 4

你应该使用例如。合并排序对数组进行排序，然后使用简单的 for 循环遍历整个数组来计算重复次数。

合并排序有 n*log(n) 和 for 循环来查找重复项也很快。

Answer 5

快速排序算法应该比 O(n^2) 快得多，并且后面跟着一个组，即 O(n) 应该仍然比 O(n^2) 快。

因此，在伪代码中：

    group (sort [1,2,3,3,2,1])   =>   [(1,2), (2,2), (3,2)] 

Answer 6

您可以通过创建另一个数据结构（例如映射）在 O(n) 时间内实现。
前任：
int a[]={1,4,1,5,2,2,4,3,4,1};

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

for(int i = 0; i < a.length ; i++)
{
    if(map.containsKey(a[i]))
    {
        map.put(a[i], map.get(a[i])+1);
    }
    else
    {
        map.put(a[i], 1);
    }
}

System.out.print(map);

结果：{1=3, 2=2, 3=1, 4=3, 5=1}

Answer 7

为什么使用二维数组？如果已知您的数字在 1..5 范围内，请使用该数字的索引：

    int a[] = {1,4,1,5,2,2,4,3,4,1};
    int b[] = new int[5];

    for (int n : a)
        ++b[n-1];

    for (int j=0; j < 5; ++j)
        System.out.println (j + " is repeated " + b [j-1] + " times");

• 不要过早声明变量，也不要重复使用它们。您会忘记删除未使用的变量（计数），并且很难分析代码。
• 使用改进的 for : 循环。
• 在头部声明计数器 - 允许这样做是有原因的： for (int i = ...) 以及为什么 i 在块外不可见。价格不贵。不，不是。查看字节码。

Answer 8

如果您可以更改现有数组，则可以执行此操作。它的 O(n log(n)) 并且不会创建新对象。 （如果你不能改变原始的，你可以克隆它。）它比维护地图更有效。 ;）

int a[] = {1, 4, 1, 5, 2, 2, 4, 3, 4, 1};

Arrays.sort(a);
int last = a[0];
int count = -1; 
for (int i : a) {
    if (i == last) {
        count++;
        continue;
    }
    System.out.println("Number " + last + " found " + count + " times.");
    count = 1;
    last = i;
}
System.out.println("Number " + last + " found " + count + " times.");

印刷

Number 1 found 3 times.
Number 2 found 2 times.
Number 3 found 1 times.
Number 4 found 3 times.
Number 5 found 1 times.

Answer 9

在这种情况下，将 O(n^2) 减少到 O(n*log n) 很简单：

1. 使用堆排序/快速排序对数字进行排序 ... O(n*log n)
2. 遍历数组一次并计算唯一元素并获取它们的计数... O(n)

保持以数字为键以及出现次数的高度平衡树是另一个想法，它将给出 O(n*log n)。如果不使用大多数语言中都可以使用的哈希表之类的数据结构，我看不到 O(n) 解决方案。