如何找出数组里出现次数超过总数1/3的数 Java实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了如何找出数组里出现次数超过总数1/3的数 Java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1017字，纯文字阅读大概需要2分钟。

内容图文

数组里出现次数超过总数1/3的数最多有两个。
三个不相同的数字为一组，删掉每一组。剩下的就是出现次数超过总数1/3的数。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        if (nums == null || nums.length == 0)
            return ans;
        int a = nums[0], cnta = 0;  //我用a b分别表示两个不一样的数
        int b = nums[0], cntb = 0;
        for (int num : nums) {
        	//1.和a相等
            if (num == a) {
                cnta++;
                continue;
            }
            //2.和b相等
            if (num == b) {
                cntb++;
                continue;
            }
            //3.没a了，将当前数设为a
            if (cnta == 0) {
                a = num;
                cnta++;
                continue;
            }
            //4.没b了，将当前数设为b
            if (cntb == 0) {
                b = num;
                cntb++;
                continue;
            }
            //5.不是新a & 不是新b & 和a不等 & 和b不等
            cnta--;//删掉一组，a计数-1
            cntb--;//删掉一组，b计数-1
        }
        cnta = 0;
        cntb = 0;
		//统计a,b在数组中出现的次数
        for (int num : nums) {
            if (num == a) {
                cnta++;
            } else if (num == b) {
                cntb++;
            }
        }
        //a出现次数超过1/3，加入结果
        if (cnta > nums.length / 3) {
            ans.add(a);
        }
        //b出现次数超过1/3，加入结果
        if (cntb > nums.length / 3) {
            ans.add(b);
        }
        return ans;
    }
}

内容总结

以上是互联网集市为您收集整理的如何找出数组里出现次数超过总数1/3的数 Java实现全部内容，希望文章能够帮你解决如何找出数组里出现次数超过总数1/3的数 Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端