相关疑难解决方法(0)

我有一个数组,填充整数.我的工作是快速找到数组的任何部分的多数元素,我需要这样做... 记录时间,而不是线性,但事先我可能需要一些时间来准备数组.

例如:

1 5 2 7 7 7 8 4 6

和查询:

[4, 7] 回报 7

[4, 8] 回报 7

[1, 2]返回0(没有多数元素),依此类推......

我需要为每个查询找到答案,如果可能的话,它需要快速执行.

为了准备,我可以使用O(n log n)时间

这是我的一个面试问题.给定N个元素的数组,其中元素恰好出现N/2次,其余N/2个元素是唯一的.你如何找到运行时间更好的元素？

请记住元素没有排序,你可以假设N是偶数.例如,

input array [] = { 10, 2, 3, 10, 1, 4, 10, 5, 10, 10 }

所以这里10次出现5次,即N/2次.

我知道O(n)运行时的解决方案.但仍期待通过O(log n)了解更好的解决方案.

例如,数组的答案:

1,11,3,95,23,8,1

将为1,因为所有其他元素仅出现一次,而1出现两次.

很多类似于我在stackoverflow上看到的这个问题的问题要求找到绝对多数(答案在长度为n的数组中至少发生n/2),或者使用排序或哈希表回答问题.前者不是我要求的,后者要么太慢(O(n log n)用于排序)或者使用太多内存(O(n)用于哈希表).

这样的算法存在吗？如果没有,是否有证据显示为什么不可能？包括一个来源会很好.

如线性时间多数算法的答案所示？,可以在线性时间和log(n)空间中计算元素数组的大部分.

结果表明,每个看过这种算法的人都认为这是一种很酷的技巧.但这个想法是否会推广到新算法？

似乎这个算法的隐藏力量在于保持一个扮演复杂角色的计数器 - 例如"(到目前为止多数元素的数量) - (到目前为止第二多数的计数)".是否存在基于相同想法的其他算法？

这是我的面试问题，对此我有些困惑。给定一个由k个元素组成的数组，设计一种线性时间算法来确定列表是否具有多数元素，其中多数元素是一个在列表中出现k / 2次以上的元素。

我试图写一个算法,如果一个数组中存在多数元素则返回true,否则返回false.编辑:我只能判断两个元素是否相等.意思是我不能使用<或>,只有=.编辑:解决方案应采用分而治之的方法.它的运行时不应该超过nlogn,我在java中写了一些东西,但我不确定它是否正确以及如何计算运行时..这是我得到的:

public static boolean MajorityBoolean(int[] arr) {
    int c;
    int n = arr.length;
    for (int i = 0; i < n; i = i + 2) {
        System.out.println("*");
        if ((arr[i] == arr[(i + 1)%n]) || ((arr[i] == arr[(i - 1+n)%n]))) {
            c = 0;
            for (int j = 0; j < n; j = j + 1)
                if (arr[j] == arr[i])
                    c = c + 1;
            if (c > n / 2)
                return true;
        }
    }
    return false;
}

有一个整数数组,长度为n.在他的一半以上的元素中,有一个k未知的常数.你不能改变阵列(他是read-only),你只有一个O(1)大小的记忆.你需要找到k最好的复杂性(你认为你可以低于O(n)？)

例:

{1, 6, 44, 1, 1, 8, 1} so k = 1

我想到了中位数,但是我不允许改变数组......

谢谢