代码之家  ›  专栏  ›  技术社区  ›  Jason Sundram Red Alert

查找数组中最常见的项

  •  23
  • Jason Sundram Red Alert  · 技术社区  · 16 年前

    将为您提供一个长度不超过2的32位无符号整数数组 32 ,其属性是数组中超过一半的项等于N,对于某些32位无符号整数N。查找N时,只需查看数组中的每个数字一次,并且最多使用2 kB内存。

    8 回复  |  直到 9 年前
        1
  •  61
  •   Jon Skeet    16 年前

    为每个位保留一个整数,并为数组中的每个整数适当增加此集合。

    最后,一些位的计数将超过数组长度的一半——这些位决定N。当然,计数将高于N出现的次数,但这并不重要。重要的是,任何不属于N的位 不能 出现超过一半的次数(因为N有超过一半的条目)和属于N的任何位 必须 发生的次数超过一半(因为它将在每次发生N以及任何额外的次数时发生)。

    (目前没有代码-即将失去网络访问权限。不过,希望上面的内容足够清楚。)

        3
  •  8
  •   Toby Speight    7 年前

    只有两个变量可以做到这一点。

    public uint MostCommon(UInt32[] numberList)
    {
        uint suspect = 0;
        int suspicionStrength = -1; 
        foreach (uint number in numberList)
        {
            if (number==suspect)
            {
                suspicionStrength++;
            }
            else
            {
                suspicionStrength--;
            }
    
            if (suspicionStrength<=0)
            {
                suspect = number;
            }
        }
        return suspect;
    }
    

    努力寻找最常见的数字,只有一个数字,即超过50%的群体。如果需要,不要急于添加检查 suspicionStrength 大于列表长度的一半-它将始终导致更全面的比较。

    另外,我还没有测试过这段代码——使用它的风险自负。

        4
  •  4
  •   Franci Penov    16 年前

    乔恩算法的伪代码(记事本C++:-)

    int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);
    
    for (int i = 0; i < lNumbers; i++)
      for (int bi = 0; bi < 32; bi++)
        arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;
    
    int N = 0;
    
    for (int bc = 0; bc < 32; bc++)
      if (arrBits[bc] > lNumbers/2)
        N = N | (1 << bc);
    
        5
  •  2
  •   Toby Speight    7 年前

    请注意,如果 a0, a1, . . . , an−1 元素的值不同,其余序列仍具有相同的引线。的确,如果我们 删除两个不同的元素,则其中只有一个元素可以作为引线。世界领袖 新序列的出现次数超过 n/2 − 1 = (n−2)/2 时代。因此,它仍然是该组织的领导人 新序列 n − 2 元素。

    下面是一个Python实现,时间复杂度为O(n):

    def goldenLeader(A):
        n = len(A)
        size = 0
        for k in xrange(n):
            if (size == 0):
                size += 1
                value = A[k]
            else:
                if (value != A[k]):
                    size -= 1
                else:
                    size += 1
        candidate = -1
        if (size > 0):
            candidate = value
        leader = -1
        count = 0
        for k in xrange(n):
            if (A[k] == candidate):
                count += 1
        if (count > n // 2):
            leader = candidate
        return leader
    
        6
  •  2
  •   Toby Speight    7 年前


    很明显,您可以通过哈希或排序来处理它,但对于潜在的无限流,您显然会耗尽内存。所以你得做点聪明的事。


    多数元素是出现在数组大小一半以上的元素

    因此,如果你计算某个元素的数量,减去所有其他元素的数量,得到数字0,那么你的原始元素就不能是多数元素。这是正确算法的基础:

    Python代码:

    def majority_element(arr):
        counter, possible_element = 0, None
        for i in arr:
            if counter == 0:
                possible_element, counter = i, 1
            elif i == possible_element:
                counter += 1
            else:
                counter -= 1
    
        return possible_element
    

    很明显,该算法是正确的 O(n) 之前有一个很小的常数 O(n) O(1) ,因为我们只初始化了三个变量。问题是这些变量中有一个是计数器,它可能会增长到 n N 你需要 O(log (n)) 空间所以 从理论上看 它是 O(n) 时间和 O(log(n)) ,你可以在一个数组中放入2^128个元素,而数组中的元素数量是难以想象的巨大。

    Boyer–Moore majority vote algorithm .

        7
  •  0
  •   Brian    16 年前

    我记得这个算法,它可能遵循也可能不遵循2K规则。它可能需要使用堆栈等重写,以避免由于函数调用而打破内存限制,但这可能是不必要的,因为它只有对数数量的此类调用。不管怎么说,我对大学里的事情有模糊的回忆,或者对这个问题有一个递归的解决方案,涉及到分而治之,秘密是当你把这些组分成两半时,其中至少有一半的值仍然超过其最大值的一半。分而治之的基本规则是你返回两个候选的最高值,其中一个是最高值,另一个是其他值(可能是第二位,也可能不是第二位)。我忘记了算法本身。

        8
  •  0
  •   Brian    16 年前

    buti-oxa/Jason Hernandez答案的正确性证明,假设Jason的答案与buti-oxa的答案相同,并且两者都按照所述算法的工作方式工作: