给定一个长度为N的数组，找出出现次数大于n/2，n/3的数，要求时间复杂度O（n），空间复杂度O(1)

　　先讨论出现次数大于n/2的数字，如果这样的数字存在，那么这个数出现的次数大于其他数出现的次数的总和。

在数组A中，我们定义两个数据集合a1,a2。a1为出现次数大于n/2的数的集合，a2为其余数组成的集合。对于数组

A中元素a、b,假设a不等于b,那么有两种情况，分别为:a属于a1,b属于a2；a属于a2,b属于a2。对于这两种情况，如

果把a、b从数组A中去掉，集合a1的size依旧是大于a2的。按照这个思路，我们有如下代码：

　　 int m;

    int count = ;

    for (auto num : nums)

   {
　　　　　// 初始的时候为1

        if ( == count)

        {

            m = num;

            ++count;

        }

        else

        {
　　　　　　　// 相等的话我们加一 不相等就同时去掉

            if (m == num)

                ++count;

            else

                --count;

        }
　　}

那么对于找出次数大于1/3的情况，我们最多存在两个这样的数字n,m。也就是说任一的n或者m与剩下的部分的比例为1:1，这就转化为求次数大于1/2的情况了。代码如下：

int m, n; //最多存在2个出现次数超过 1/3 的元素

    int cm, cn; //对应 m 和 n 的统计

    for (auto num : nums) {

        if (cm ==  || num == m) {

            m = num;

            ++cm;

        }

        else if (cn ==  || num == n) {

            n = num;

            ++cn;

        }

        else {

            --cm;

            --cn;

        }

    }
　　

　　if(cm > (cn+cm)/3) cout << m <<endl;
　　if(cn > (cn+cm)/3) cout << n << endl;

可以简单的理解为，如果从不超过1/3的那部分数据中去掉一个数字，那么n,m对应的数据集合分别要去掉一个数字，n,m对应的数据集size大于1/3的条件才不会变。

上面有一个假设是有解的，对于无解的情况，还需要额外的遍历一次进行验证。

给定一个长度为N的数组，找出出现次数大于n/2，n/3的数，要求时间复杂度O（n），空间复杂度O(1)的相关教程结束。