主页 / 问题 / 1386657
Accepted
Pavel
Asked:2022-08-01 23:36:51 +0000 UTC2022-08-01 23:36:51 +0000 UTC

O(n) 中 2x 排序数组中最常见的元素

  • 772

找出按升序排序的两个数组的并集中出现频率最高的元素的次数。元素可以重复。该算法必须在线性时间内运行。并且无法创建额外的数组以节省内存。

findMaxCount([1, 2, 9, 10], [2, 2, 10]) => 3

这个问题在面试中被抓到，我无法解决。据我了解，为了实现线性时间，您需要移动 2 个指针，但具体如何尚不清楚。

java

2 个回答

  1. Best Answer

    两个指针和一个盒子在帽子里

    int findMaxCount(int[] data1, int[] data2)
{
    int ind1=0; 
    int ind2=0;
        
    int last = 0;
    int lastCount = 0;

    int max = 0;
    int maxCount = 0;   
    
    while(ind1 < data1.Length || ind2 < data2.Length)
    {
        int cur = 0;

        if (ind1 == data1.Length)
            cur = data2[ind2++];        
        else if (ind2 == data2.Length)      
            cur = data1[ind1++];
        else if (data1[ind1] < data2[ind2])         
            cur = data1[ind1++];
        else
            cur = data2[ind2++];
            
        if (cur == last) lastCount++;
        else 
        {
            if (lastCount > maxCount)
            {
                maxCount = lastCount;
                max = last;
            }
            last = cur;
            lastCount = 1;
        }
    }

    if (lastCount > maxCount)
    {
        maxCount = lastCount;
        max = last;
    }

    return max;
}

    考试

    System.out.println(findMaxCount(new[] { 1, 2, 8, 10 }, new[] {2, 2, 3, 3, 10}));

    结论

    2
    • 2

  2. 有一个相当著名的归并排序算法。它有一个合并阶段，当给定两个排序数组时，必须将它们组合成一个排序数组。

    这是应该使用的算法。您只需要记住最后一个元素并计算它遇到的次数，而不是写入数组。并且如果当前与前一个不一致，那么我们检查是否需要更新结果。

    • 1

相关问题