/**
* Created by clearbug on 2018/2/26.
*
* 面试题39:数组中出现次数超过一半的数字
*/
public class Solution {
public static void main(String[] args) throws InterruptedException {
Solution s = new Solution();
int[] arr = {1, 2, 3, 2, 2, 2, 5, 4, 2};
System.out.println(s.moreThanHalf1(arr));
System.out.println(s.moreThanHalf2(arr));
}
/**
* 首先说一下最简单却有不那么容易让人想到的方法:数组中有一个数字出现的次数超过数组长度的一半,也就是说它出现的次数比其他所有数字出现
* 的次数的和还要多。
*
* 时间复杂度:O(n)
*
* @param arr
* @return
*/
public int moreThanHalf1(int[] arr) {
int res = arr[0];
int times = 1;
for (int i = 1; i < arr.length; i++) {
if (times == 0) {
res = arr[i];
times = 1;
} else if (arr[i] == res){
times++;
} else {
times--;
}
}
return res;
}
/**
* 第二种方法就是借助快速排序的思想:当数组大致有序时,出现次数超过一半的数字必然是位于数组的中间位置
*
* 时间复杂度:O(n)
*
* @param arr
* @return
*/
public int moreThanHalf2(int[] arr) {
int middle = arr.length >> 1;
int start = 0;
int end = arr.length - 1;
int index = partition(arr, start, end);
while (index != middle) {
if (index > middle) {
end = index - 1;
index = partition(arr, start, end);
} else {
start = index + 1;
index = partition(arr, start, end);
}
}
return arr[middle];
}
private int partition(int[] arr, int start, int end) {
int privot = arr[start];
while (start < end) {
while (arr[end] >= privot && end > start) {
end--;
}
arr[start] = arr[end];
while (arr[start] <= privot && end > start) {
start++;
}
arr[end] = arr[start];
}
arr[start] = privot;
return start;
}
}
面试题39:数组中出现次数超过一半的数字
程序员文章站
2024-02-27 15:50:15
...
上一篇: 146-最近使用缓存