为数组中大小为 k 的每个 window 查找模式

Question

给定一个大小为 n 和 k 的数组，如何找到大小为 k 的每个连续子数组的模式？

例如

arr = 1 2 2 6 6 1 1 7 
k = 3 
ans = 2 2 6 6 1 1

我正在考虑拥有一个哈希图，其中键为 no，值为频率，树形图，其中键为频率，值为数字，并有一个队列在大小 > k 时删除第一个元素。这里的时间复杂度是o(nlog(n))。我们可以在 O(1) 中做到这一点吗？

Answer 1

这可以在 O(n) 时间内完成

我对这个问题很感兴趣，部分原因是，正如我在评论中指出的那样，我确信它可以在 O(n) 时间内完成。上周末我有一些时间，所以我写了解决这个问题的方法。

方法：模式频率

基本概念是这样的：数字集合的模式是该集合中出现频率最高的数字。

这意味着无论何时向集合中添加一个数字，如果添加的数字还不是模式值之一，那么模式的频率就不会改变。因此，对于集合 (8 9 9)，模式值为 {9}，模式频率为 2。如果您将 5 添加到此集合 ((8 9 9 5))，模式频率和模式值都不会改变。相反，如果您将 8 添加到集合 ((8 9 9 8))，则模式值将更改为 {9, 8}，但模式频率仍未更改为 2。最后，如果您改为将 9 添加到集合 ((8 9 9 9))，现在模式频率会增加一个。

因此，在所有情况下，当您向集合中添加一个数字时，模式频率要么不变，要么只增加一个。同样，当您从集合中删除单个数字时，模式频率要么保持不变，要么最多下降一个。因此，对集合的所有增量更改只会导致两种可能的新模式频率。这意味着如果我们将集合中所有不同的数字都按频率索引，那么我们总能在恒定的时间内找到新的模式（即 O(1)）。

为了完成这个，我使用了一个自定义数据结构（“ModeTracker”），它有一个 multiset（“numFreqs”）来存储集合的不同数字以及它们在集合中的当前频率。这是用 Dictionary 实现的（我认为这是 Java 中的 Map）。因此给定一个数字，我们可以使用它在 O(1) 的集合中找到它的当前频率。

此数据结构还有一个集合数组（“freqNums”），给定一个特定的频率将 return 当前集合中具有该频率的所有数字。

我在下面包含了这个数据结构的代码 class。请注意，这是在 C# 中实现的，因为我对 Java 的了解还不足以在那里实现它，但我相信 Java 程序员在翻译它时应该没有问题。

（伪）代码：

class ModeTracker
{
    HashSet<int>[] freqNums;        //numbers at each frequency
    Dictionary<int, int> numFreqs;  //frequencies for each number
    int modeFreq_ = 0;              //frequency of the current mode

    public ModeTracker(int maxFrequency)
    {
        freqNums = new HashSet<int>[maxFrequency + 2];
        // populate frequencies, so we dont have to check later
        for (int i=0; i<maxFrequency+1; i++)
        {
            freqNums[i] = new HashSet<int>();
        }

        numFreqs = new Dictionary<int, int>();
    }

    public int Mode { get { return freqNums[modeFreq_].First(); } }

    public void addNumber(int n)
    {
        int newFreq = adjustNumberCount(n, 1);

        // new mode-frequency is one greater or the same 
        if (freqNums[modeFreq_+1].Count > 0) modeFreq_++;
    }

    public void removeNumber(int n)
    {
        int newFreq = adjustNumberCount(n, -1);

        // new mode-frequency is the same or one less
        if (freqNums[modeFreq_].Count == 0)  modeFreq_--;
    }

    int adjustNumberCount(int num, int adjust)
    {
        // make sure we already have this number
        if (!numFreqs.ContainsKey(num))
        {
            // add entries for it
            numFreqs.Add(num, 0);
            freqNums[0].Add(num);
        }

        // now adjust this number's frequency
        int oldFreq = numFreqs[num];
        int newFreq = oldFreq + adjust;
        numFreqs[num] = newFreq;

        // remove old freq for this number and and the new one
        freqNums[oldFreq].Remove(num);
        freqNums[newFreq].Add(num);

        return newFreq;
    }
}

此外，下面是一个小的 C# 函数，演示了如何使用此数据结构来解决问题中最初提出的问题。

    int[] ModesOfSubarrays(int[] arr, int subLen)
    {
        ModeTracker tracker = new ModeTracker(subLen);
        int[] modes = new int[arr.Length - subLen + 1];

        for (int i=0; i < arr.Length; i++)
        {
            //add every number into the tracker
            tracker.addNumber(arr[i]);

            if (i >= subLen)
            {
                // remove the number that just rotated out of the window
                tracker.removeNumber(arr[i-subLen]);
            }

            if (i >= subLen - 1)
            {
                // add the new Mode to the output
                modes[i - subLen + 1] = tracker.Mode;
            }
        }

        return modes;
    }

我已经对此进行了测试，它似乎在我的所有测试中都能正常工作。

复杂度分析

通过 `ModesOfSubarrays()` 函数的各个步骤：

新的 ModeTracker 对象在 O(n) 或更短时间内创建。
modes[] 数组在 O(n) 时间内创建。
For(..) 循环 N 次： . 3a：addNumber() 函数需要 O(1) 时间 . 3b：removeNumber() 函数需要 O(1) 时间 . 3c: 获取新模式需要 O(1) 时间

所以总时间是O(n) + O(n) + n*(O(1) + O(1) + O(1)) = O(n)

如果您对此代码有任何疑问，请告诉我。

为数组中大小为 k 的每个 window 查找模式

Finding mode for every window of size k in an array

java

arrays

algorithm

data-structures

这可以在 O(n) 时间内完成

方法：模式频率

（伪）代码：

复杂度分析