找出数组中次数超过n/2或n/3的数

题目描述

找出数组中出现次数超过n/2的数。

输入：

7
1 2 1 3 1 1 4

输出：

1

思路：

找出两个不相同的数消除，最终剩下的一定是超过一半的数。

代码：

import java.util.*;
public class Main {
    public static void main(String arg[]){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            int nums[] = new int[n];
            for (int i=0; i<n; i++){
                nums[i] = in.nextInt();
            }
            int res = nums[0], count = 1;
            for (int i=1; i<n; i++){
                if (nums[i] == res){
                    count++;
                }
                else {
                    if (count == 0){
                        res = nums[i];
                        count = 1;
                    }
                    else {
                        count--;
                    }
                }
            }
            System.out.println(res);
        }
    }
}

题目描述

找出数组中出现次数超过n/3的数，样例保证该数唯一。

输入：

7
1 2 1 3 1 2 4

输出：

1

思路：

当找到3个互不相同的数时进行消除，最终留下两个数，再遍历一遍看两个数出现的次数即可。

代码：

import java.util.*;
public class Main {
    public static void main(String arg[]){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            int nums[] = new int[n];
            for (int i=0; i<n; i++){
                nums[i] = in.nextInt();
            }
            int a = 0, countA = 0, b = 0, countB = 0;
            for (int i=0; i<n; i++){
                if (a == nums[i]) countA++;
                else if (b == nums[i]) countB++;
                //每一个与a和b都不同的数都会让a、b的数量减1
                else {
                    //当a、b的数量为0的时候自然换上新的数
                    if (countA == 0){
                        a = nums[i];
                        countA = 1;
                    }
                    else if (countB == 0){
                        b = nums[i];
                        countB = 1;
                    }
                    else {
                        countA--;
                        countB--;
                    }
                }
            }
            //出现超过n/3的数必定为a、b中的一个
            countA = 0;
            countB = 0;
            for (int i=0; i<n; i++){
                if (nums[i] == a) countA++;
                if (nums[i] == b) countB++;
            }
            int res;
            if (countA > n/3) res = a;
            else res = b;
            System.out.println(res);
        }
    }
}