//數(shù)組中出現(xiàn)次數(shù)超過(guò)一般的數(shù)字
public class MoreThanHalfNum {
// 判斷數(shù)組是否為空
public static boolean checkInvalidArray(int[] numbers) {
if (numbers == null || numbers.length == 0)
return true;
return false;
}
// 基于快速排序算法的partition函數(shù)
public static int partition(int[] numbers, int left, int right) {
int result = numbers[left];
if (left > right) {
return -1;
}
while (left < right) {
while (left < right && numbers[right] >= result) {
right--;
}
numbers[left] = numbers[right];
while (left < right && numbers[left] < result) {
left++;
}
numbers[right] = numbers[left];
}
numbers[left] = result;
return left;
}
// 判斷中間的元素出現(xiàn)的次數(shù)是否超過(guò)數(shù)組長(zhǎng)度的一半
public static boolean checkMoreThanHalf(int[] numbers, int length, int result) {
int times = 0;
for (int i = 0; i < length; i++) {
if (numbers[i] == result) {
times++;
}
}
if (times * 2 > length)
return true;
return false;
}
// 找出數(shù)組的中位數(shù)奖蔓，并放到中間位置 基于Partition函數(shù)的O(n)算法
public static int moreThanHalfNum(int[] numbers) {
if (checkInvalidArray(numbers))
return 0;
int length = numbers.length;
int middle = length / 2;
int start = 0;
int end = length - 1;
int index = partition(numbers, start, end);
while (index != middle) {
if (index > middle) {
end = index - 1;
index = partition(numbers, start, end);
} else {
start = index + 1;
index = partition(numbers, start, end);
}
}
int result = numbers[middle];
if (!checkMoreThanHalf(numbers, length, result)) {
return 0;
}
return result;
}
// 根據(jù)數(shù)組特點(diǎn)求出O(n)的算法
public static int moreThanHalfNum2(int[] numbers) {
if (checkInvalidArray(numbers))
return 0;
int result = numbers[0];
int times = 1;
for (int i = 1; i < numbers.length; i++) {
if (times == 0) {
result = numbers[i];
times = 1;
} else {
if (numbers[i] == result) {
times++;
} else {
times--;
}
}
}
if (!checkMoreThanHalf(numbers, numbers.length, result)) {
return 0;
}
return result;
}
public static void main(String[] args) {
int[] numbers = { 3, 3, 3, 3, 2, 2, 1 };
System.out.println(moreThanHalfNum(numbers));
System.out.println(moreThanHalfNum2(numbers));
}
}
