1.数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解法1：通过Partition函数，找到中位数的下标，则该数即为目标数
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int len = 0;
if (array == null || (len = array.length) == 0) return 0;
int mid = len >> 1;
int pivotIndex = Partition(array,0, len - 1);
while (pivotIndex != mid) {
if (pivotIndex > mid) {
pivotIndex = Partition(array, 0, pivotIndex - 1);
} else {
pivotIndex = Partition(array, pivotIndex + 1, len - 1);
}
}
int target = array[mid];
int count = 0;
for (int i = 0; i < len; i++) {
if (array[i] == target) {
count++;
}
}
if (count*2 <= len) {
return 0;
}
return target;
}
private int Partition(int[] arr, int L, int R) {
int pivot = arr[L];
while (L < R) {
while (L < R && arr[R] >= pivot) R--;
arr[L] = arr[R];
while (L < R && arr[L] <= pivot) L++;
arr[R] = arr[L];
}
arr[L] = pivot;
return L;
}
}
解法2：按顺序扫描数组，并记录扫描到的数字和它出现的次数，如果下一个数是这个数字，次数加一，否则次数减一，如果次数为0则更换记录的数字并将次数重置为1，直到最后出现次数大于等于1的记录的数字，则该数字就是目标数字
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int len = 0;
if (array == null || (len = array.length) == 0) return 0;
int target = array[0];
int count = 1;
for (int i = 1; i < len; i++) {
if (count == 0) {
target = array[i];
count = 1;
} else {
if (array[i] == target){
count++;
} else {
count--;
}
}
}
count = 0;
for (int i = 0; i < len; i++) {
if (array[i] == target) {
count++;
}
}
if (count * 2 <= len) {
return 0;
}
return target;
}
}
边界条件出错了！
2.最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
解法1：通过Partition函数，找到第K个数的下标，则该数即为目标数
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
int len = 0;
ArrayList<Integer> list = new ArrayList<Integer>();
if (input == null || (len = input.length) <= 0 || k > len || k <= 0) return list;
int pivotIndex = Partition(input, 0, len - 1);
while (pivotIndex != (k - 1)) {
if (pivotIndex > k) {
pivotIndex = Partition(input, 0, pivotIndex - 1);
} else {
pivotIndex = Partition(input, pivotIndex + 1, len - 1);
}
}
for (int i = 0; i < k; i++) {
list.add(input[i]);
}
return list;
}
private int Partition(int[] arr, int L, int R) {
int pivot = arr[L];
while (L < R) {
while (L < R && arr[R] >= pivot) R--;
arr[L] = arr[R];
while (L < R && arr[L] <= pivot) L++;
arr[R] = arr[L];
}
arr[L] = pivot;
return L;
}
}
一定要注意每一个边界条件：if (input == null || (len = input.length) <= 0 || k > len || k <= 0) return list;
解法2（不修改原数组）：新建一个长度为k的新集合，按顺序扫描数组并添加进该集合中，集合满了以后，比较数组下一个数跟集合中最大数的大小，如果小于，则替换集合中的最大值，直到扫描数组结束
注：集合可以是大根堆或者红黑树
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>(k);
int len = 0;
if (input == null || (len = input.length) <= 0 || k > len || k <= 0) return list;
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int i = 0; i < len; i++) {
if (i < k) {
maxHeap.offer(input[i]);
} else {
if (input[i] < maxHeap.peek()) {
maxHeap.poll();
maxHeap.offer(input[i]);
}
}
}
for (Integer i : maxHeap) {
list.add(i);
}
return list;
}
}
优先队列和比较器的使用，可以看作是大根堆！
新知识：PriorityQueue 优先队列
- PriorityQueue通过二叉小顶堆实现。
- 作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素）。
- 元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）
- 比较器（Comparator）
- 比较器分为两种Comparable和Comparator
- Comparable：实现Comparable接口，并且重写compareTo(T o)方法
- Comparator：实现Comparator接口，并且重写compare()和equals()方法
- int compare(Object o1, Object o2) 返回一个基本类型的整型
- 如果要按照升序排序o1.compareTo(o2),则o1 小于o2，返回-1（负数），相等返回0，01大于02返回1（正数）
- 如果要按照降序排序o2.compareTo(o1),则o1 小于o2，返回1（正数），相等返回0，01大于02返回-1（负数）
- add()和offer()：前者在插入失败时抛出异常，后则则会返回false。
- element()和peek()：都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。
- remove()和poll()：获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。
