乐趣区

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

数组中呈现次数超过一半的数字

题目形容

数组中有一个数字呈现的次数超过数组长度的一半,请找出这个数字。例如输出一个长度为 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;
    }
}

【每日寄语】不辜负每一个太阳升起的日子,不辜负身边每一场花开,不辜负身边一点一滴的领有。

退出移动版