题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&&tqId=11181&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
O(n)时间复杂度
O(1)空间复杂度
- 一趟遍历，O(1)的空间消耗，意味着就地处理。
- 超过一半，意味着出现的次数多于
public class Solution {
public int MoreThanHalfNum_Solution(int [] a) {
int cand = a[0];
int times = 1;
for (int i = 1; i < a.length; i++) {
if (times == 0) {
cand = a[i]; // 放弃上一个候选，重新选取
times = 1;
} else if (a[i] == cand) {
times++; // 候选的次数加1
} else {
times--; // 候选的次数消减1
}
}
return cand;
}
} 
查看15道真题和解析