今日题目（对应书上第39~42题）：

1. 数组中出现次数超过一半的数字
2. 最小的k个数（top k，重点！）
3. 数据流中的中位数
4. 连续子数组的最大和

今天的题目都比较经典，特别是第2题。

1. 数组中出现次数超过一半的数字

题目描述：
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：
有两种方法，
一，利用类似于快排的思想，寻找数组中的中位数，然后再检查是否满足出现次数。
二，根据数组的特点来做。

代码如下：

//方法一，快排
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0) return 0;
int start = 0, end = array.length-1;
int mid = array.length>>1;
while(start < end){ int ind = partition(array,start,end); if(ind == mid) break; if(ind > mid)
end = ind-1;
if(ind < mid)
start = ind+1;
}
if(check(array,array[mid]))
return array[mid];
else return 0;
}

 public boolean check(int\[\] nums,int result){  
     int times = 0;  
     for(int n:nums){  
         if(n == result)  
             times++;  
     }  
     return times\*2 > nums.length;  
 }

 public int partition(int\[\] nums,int start,int end){  
     int target = nums\[end\];  
     int res = start;  
     for(int i = start; i < end; i++){  
         if(nums\[i\] < target){  
             int swap = nums\[i\];  
             nums\[i\] = nums\[res\];  
             nums\[res\] = swap;  
             res++;  
         }  
     }  
     nums\[end\] = nums\[res\];  
     nums\[res\] = target;  
     return res;  
 }  

}

//方法二
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length == 0) return 0;
int result = array[0];
int times = 1;
for(int n:array){
if(times == 0){
result = n;
times = 1;
}else if(result == n)
times++;
else
times--;
}
if(check(array,result))
return result;
else return 0;
}

2. 最小的k个数

题目描述：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路：
这道题是经典的top K问题，有两种解法：
1,运用快排，找出第K个数的位置，将前面的数输出
2,利用容量为K的最大堆，循环数组，每次替换掉堆中最大的数

代码如下：

//快排
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList res = new ArrayList();
if(k > input.length || k == 0) return res;
int start = 0, end = input.length-1;
int ind = partition(input,start,end);
while(ind != k-1){
if(ind > k-1){
end = ind-1;
}else{
start = ind+1;
}
ind = partition(input,start,end);
}
for(int i = 0;i < k; i++)
res.add(input[i]);
return res;
}

 public int partition(int\[\] nums,int start,int end){  
     int target = nums\[end\];  
     int ind = start;  
     for(int i = start; i < end;i++){  
         if(nums\[i\] < target){  
             int swap = nums\[i\];  
             nums\[i\] = nums\[ind\];  
             nums\[ind\] = swap;  
             ind++;  
         }  
     }  
     nums\[end\] = nums\[ind\];  
     nums\[ind\] = target;  
     return ind;  
 }  

}

//利用最大堆
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
if(k > input.length || k < 1) return new ArrayList(); PriorityQueue maxHeap = new PriorityQueue(k,new Comparator(){
public int compare(Integer o1,Integer o2){
return o2.compareTo(o1);
}
});
for(int i = 0; i < input.length; i++){ if(maxHeap.size() < k) maxHeap.add(input[i]); else{ if(maxHeap.peek() > input[i]){
maxHeap.poll();
maxHeap.add(input[i]);
}
}
}
return new ArrayList(maxHeap);
}
}

3.数据流中的中位数

题目描述：
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

思路：
这道题的关键是选择一个怎样的数据结构来维护数据流，可以使插入和查询的速度都比较理想。在这边维护了一个最大堆和一个最小堆，最大堆存储中位数左边的数字，最小堆存储中位数右边的数字。

代码如下：

public class Solution {
int count = 0;
PriorityQueue min = new PriorityQueue();
PriorityQueue max = new PriorityQueue(new Comparator(){
public int compare(Integer o1,Integer o2){
return o2-o1;
}
});
public void Insert(Integer num) {
if((count&1) == 0){
min.offer(num);
max.offer(min.poll());
}else{
max.offer(num);
min.offer(max.poll());
}
count++;
}

 public Double GetMedian() {  
     if(((min.size()+max.size())&1) == 0)  
         return (min.peek()+max.peek())/2.0;  
     else  
         return max.peek()\*1.0;  
 }  

}

4.连续子数组的最大和

题目描述：
输入一个整数数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

思路：
这道题也算是比较经典的一道题了，面经里面经常看到，下面给出两种解法。

代码如下：

//解法一
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int max = Integer.MIN_VALUE;
int sum = 0;
for(int n:array){
if(sum <= 0) sum = n; else sum += n; max = max>sum?max:sum;

     }  
     return max;  
 }  

}

//解法二，动态规划
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int[] dp = new int[array.length];
dp[0] = array[0];
for(int i = 1; i < array.length; i++){ if(dp[i-1] < 0) dp[i] = array[i]; else dp[i] = array[i] + dp[i-1]; } int res = dp[0]; for(int n:dp) res = n>res?n:res;
return res;
}
}