mrtalent的专栏

原创 求数组中出现次数超过一半的数

一个数组a[0...n-1]，O（n）时限，算出现次数大于n/2的那个数b。 由于b占一半以上，初步思想就是每次都让两个数相互删去，最后就留下b了。 每次至少删掉当前数组一半的数，1+1/2+1/4+...=2,复杂度2n 具体： 每次让第1\2个数比较，相同就留一个，不同就都删掉，如果数组的个数是奇数，最后一个先留着，叫res，这个res有用。 然后求新的数组。如果新的