數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。
你可以假設數組是非空的，并且給定的數組總是存在多數元素。
示例?1:
輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
輸出: 2
限制：
1 <= 數組長度 <= 50000
思路：
打擂臺法：
擂主和打擂者不一樣，就減一條命。擂主和打擂者一樣，就加一條命。
擂主生命被減為0，就下臺，由挑戰者上臺。
最后在擂臺上的人就是答案。
正確性：我們假象：那個傳說中出現次數一半以上的數字x和剩下的人對抗，最終結果是，x獲勝，生命至少還有1，對吧。
真實情況：不是x的數字不僅會減x的生命值，還會“內耗”，也就是互相減生命，所以無論如何x將是最后的勝利者。
class Solution {public int majorityElement(int[] nums) {int target=nums[0];//擂臺上的人int num=1;//擂臺上的人的生命for(int i=0;i<nums.length;i++){if(nums[i]!=target){num--;}else{num++;}if(num==0){num=1;target=nums[i];}}return target;}
}輸入整數數組 arr ，找出其中最小的 k 個數。例如，輸入4、5、1、6、2、7、3、8這8個數字，則最小的4個數字是1、2、3、4。
示例 1：
輸入：arr = [3,2,1], k = 2
輸出：[1,2] 或者 [2,1]
示例 2：
輸入：arr = [0,1,2,1], k = 1
輸出：[0]
?
限制：
0 <= k <= arr.length <= 10000
0 <= arr[i]?<= 10000
思路：快排，根據一趟排出的情況只對一邊繼續即可。
重點：：：：：：：：：：
????????????while(i<j?&&?arr[j]>=key)j--;
????????????arr[i]=arr[j];
????????????while(i<j?&&?arr[i]<=key)i++;
????????????arr[j]=arr[i];
不加那個等于號就超時，不知道為啥。
class Solution {public int[] getLeastNumbers(int[] arr, int k) {help(arr,k,0,arr.length-1);return Arrays.copyOf(arr, k);}public void help(int[] arr,int k,int left,int right){if(left>=right || left>=k)return;int key=arr[left];int i=left;int j=right;while(i<j){while(i<j && arr[j]>=key)j--;arr[i]=arr[j];while(i<j && arr[i]<=key)i++;arr[j]=arr[i];}arr[i]=key;if(k <= j) help(arr,k, left, j-1);else help(arr, k, j + 1, right);}
}如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。
例如，
[2,3,4]?的中位數是 3
[2,3] 的中位數是 (2 + 3) / 2 = 2.5
設計一個支持以下兩種操作的數據結構：
void addNum(int num) - 從數據流中添加一個整數到數據結構中。
double findMedian() - 返回目前所有元素的中位數。
示例 1：
輸入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
輸出：[null,null,null,1.50000,null,2.00000]
示例 2：
輸入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
輸出：[null,null,2.00000,null,2.50000]
?
限制：
最多會對?addNum、findMedia進行?50000?次調用。
思路：維護一個大根堆一個小根堆，分別記錄小的一半和大的一半。采用任何策略，可以維護兩個堆大小一樣即可（我的策略中小的一半可以多一個，也就是說多那個中位數）。
class MedianFinder {private PriorityQueue<Integer> maxHeap, minHeap;public MedianFinder() {maxHeap = new PriorityQueue<>(Collections.reverseOrder());minHeap = new PriorityQueue<>();}public void addNum(int num) {maxHeap.offer(num);minHeap.offer(maxHeap.poll());//調整：maxHeap始終=minHeap或minHeap+1if (minHeap.size() > maxHeap.size()) {maxHeap.offer(minHeap.poll());}}public double findMedian() {if (maxHeap.size() == minHeap.size()) {return (maxHeap.peek() + minHeap.peek()) * 0.5;}return maxHeap.peek();}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/輸入一個整型數組，數組里有正數也有負數。數組中的一個或連續多個整數組成一個子數組。求所有子數組的和的最大值。
要求時間復雜度為O(n)。
?
示例1:
輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋:?連續子數組?[4,-1,2,1] 的和最大，為?6。
?
提示：
1 <=?arr.length <= 10^5
-100 <= arr[i] <= 100
思路：簡單dp不解釋。
class Solution {public int maxSubArray(int[] nums) {int ans=Integer.MIN_VALUE;int num=0;for(int i:nums){num=num>0?num+i:i;if(num>ans)ans=num;}return ans;}
}?
