題目：

? ? 給定一個數組arr，求出需要排序的最短子數組長度

要求：

? ? 時間o(n),空間o(1)

思路：

? ? 有序的數組中，任意一個數字，一定小于左邊的數大于右邊的數。

? ? 我們找到的需要排序的子數組，顯然是比右邊最小的值大，或比左邊最大的值小。

? ? 我們初始化變量noMinindex=-1;從右往左遍歷，記錄經過的最小值為min，若當前數大于min，說明，如果要有序，min一定要放? ? ? 在當前數左邊，我們更新noMinindex。

? ? 也就是說，我們的noMinindex是負責記錄最左邊出現這種情況的位置。我們反方向處理出noMaxindex

? ? 他們組成的區間就是最短需要排序的部分了

public class MinLengthForSort {public static int getMinLength(int[] arr) {if (arr == null || arr.length < 2) {return 0;}int min = arr[arr.length - 1];int noMinIndex = -1;for (int i = arr.length - 2; i != -1; i--) {if (arr[i] > min) {noMinIndex = i;} else {min = Math.min(min, arr[i]);}}if (noMinIndex == -1) {return 0;}int max = arr[0];int noMaxIndex = -1;for (int i = 1; i != arr.length; i++) {if (arr[i] < max) {noMaxIndex = i;} else {max = Math.max(max, arr[i]);}}return noMaxIndex - noMinIndex + 1;}public static void main(String[] args) {int[] arr = { 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19 };System.out.println(getMinLength(arr));}}

?

題目：

? ? 給定一個數組，找出出現次數超過一半的數字

蠢思路：排序找中間

思路：

? ? DP：掃一遍一個變量count記錄解出現的次數，是當前解就++，否則--，count為負就換掉當前解。（解釋：想象解全都挨在? ? ? ? ?一起（前面），count先達到最大，然后減為1或0，而其他數字先出現，可能會使正確解的count減為負數，但都會使正確解? ? ? ? 在后面更多，從而保證了結束時肯定為正確解）

int main()
{int n;//個數scanf("%d",&n);int temp,k,count=0;while(n--){scanf("%d",&temp);if(temp==k)count++;else{count--;if(count<0){count=0;k=temp;}}}printf("%d\n",k);
}

?

?

題目：

給定一個有N×M的整型矩陣matrix和一個整數K，matrix的每一行和每一列都是排好序的。實現一個函數，判斷K是否在matrix中。

例如：

0???????1???????2???????5

2???????3???????4???????7

4???????4???????4???????8

5???????7???????7???????9

如果K為7，返回true，如果K為6，返回false

要求：

時間復雜度為O(N+M)，額外空間復雜度為O(1)。

思路：

1.從矩陣最右上角的數開始尋找（row=0,col=M-1）。

2.比較當前數matrix[row][col]與K的關系：

如果與K相等，說明已找到，直接返回true

如果比K大，因為矩陣每一列都已排好序，所以在當前數所在的列中，處于當前數下方的數都會比K大，則沒有必要繼續在第col列上尋找，令col=col-1，重復步驟2.

如果比K小，因為矩陣每一行都已排好序，所以在當前數所在的行中，處于當前數左方的數都會比K小，則沒有必要繼續在第row行上尋找，令row=row+1,重復步驟2.

3.如果找到越界都沒有發現與K相等的數，則返回false。

或者可以從矩陣的最左下角的數開始尋找（row=N-1,col=0），具體過程類似。

代碼：
?

/*** 在行列都排好序的矩陣中找數*/
public class IsContains {public boolean isContains(int[][] matrix, int K) {int row = 0;int col = matrix[0].length - 1;while (row < matrix.length && col > -1) {if (matrix[row][col] == K) {return true;} else if (matrix[row][col] > K) {col--;} else {row++;}}return false;}
}

?