关于java:JZ028数组中出现次数超过一半的数字

31次阅读

共计 779 个字符，预计需要花费 2 分钟才能阅读完成。

数组中有一个数字呈现的次数超过数组长度的一半，请找出这个数字。例如输出一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。因为数字 2 在数组中呈现了 5 次，超过数组长度的一半，因而输入 2。如果不存在则输入 0。

题目链接 : 数组中呈现次数超过一半的数字

/**
 * 题目：数组中呈现次数超过一半的数字
 * 题目形容
 * 数组中有一个数字呈现的次数超过数组长度的一半，请找出这个数字。例如输出一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。* 因为数字 2 在数组中呈现了 5 次，超过数组长度的一半，因而输入 2。如果不存在则输入 0。* 题目链接：* https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 */
public class Jz28 {public int moreThanHalfNum_Solution(int[] array) {int majority = array[0];
        for (int i = 1, cnt = 1; i < array.length; i++) {if (array[i] == majority) {cnt++;} else {cnt--;}
            if (cnt == 0) {majority = array[i];
                cnt = 1;
            }
        }
        int cnt = 0;
        for (int val : array) {if (val == majority) {cnt++;}
        }
        return cnt > array.length / 2 ? majority : 0;
    }
}