剑指Offer Java版 面试题39：数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
练习地址
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
解法一：基于Partition函数的时间复杂度为O(n)的算法
public class Solution {
public int MoreThanHalfNum_Solution(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int middle = array.length >> 1, start = 0, end = array.length - 1;
int index = partition(array, start, end);
while (index != middle) {
if (index > middle) {
end = index - 1;
} else {
start = index + 1;
}
index = partition(array, start, end);
}
int result = array[middle], times = 0;
for (int number : array) {
if (number == result) {
times++;
}
}
return times > array.length >> 1 ? result : 0;
}
// 基于《算法（第4版）》的快速排序算法代码
private int partition(int[] a, int lo, int hi) {
if (lo == hi) {
return lo;
}
int i = lo, j = hi + 1;
int v = a[lo];
while (true) {
while (a[++i] < v) {
if (i == hi) {
break;
}
}
while (v < a[--j]) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
private void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
解法二：根据数组特点找出时间复杂度为O(n)的算法
public class Solution {
public int MoreThanHalfNum_Solution(int[] array) {
if (array == null || array.length == 0) {
return 0;
}
int result = 0, times = 0;
for (int number : array) {
if (times == 0) {
result = number;
times = 1;
} else if (number == result) {
times++;
} else {
times--;
}
}
times = 0;
for (int number : array) {
if (number == result) {
times++;
}
}
return times > array.length >> 1 ? result : 0;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
