題目一

給定一個長度為N的整型數組arr，其中有N個互不相等的自然數1~N

請實現arr的排序

但是不要把下標0~N-1位置上的數值通過直接賦值的方式替換成1~N。

要求：時間復雜度為O(N)，額外空間復雜度為O(1)。

?

思路：從左向右檢查，檢查到需要換的以后，就直接把它放到該去的位置，然后被換掉的數，位置肯定也不對，繼續重復相同的方法，最后肯定會跳回來（原因懶得說了自己想想），然后繼續往下檢查即可。

public static void sort1(int[] arr) {int tmp = 0;int next = 0;for (int i = 0; i != arr.length; i++) {tmp = arr[i];while (arr[i] != i + 1) {next = arr[tmp - 1];arr[tmp - 1] = tmp;tmp = next;}}}

題目二

本題一般思路：依次查找找到比前后都小的數；或者選出最小數，他肯定是局部最小的；等等

但這些都是O(n)的方法，而用二分可以做到O(logn).

二分思路：

??考慮最左和最右的元素：如果arr[0]<arr[1] ?return?0; arr[N-1]<arr[N-2] return?N-1;

???考慮最中間元素，如果中間元素大于它左邊的元素，那么局部最小值就應該在數組的左半部分

???如果中間元素小于大于它右邊的元素，那么局部最小值就應該在數組的右半部分

???中間元素既小于它左邊的值又小于它右邊的值，那么它就是局部最小
?

題目三

?

給定一個整數數組arr，返回不包含本位置的累乘數組。

比如2 3 1 4返回12 8 24 6

方法一：算出所有數的乘積，每個位置除以自己即可。要注意坑：如果數組中有一個0，那么0這個位置就是其他數的乘積，其他位置全為0；如果有多個0，那么所有位置都是0.

	public int[] product1(int[] arr) {if(arr==null || arr.length<2) {return null;}int count=0;//0的個數int all=1;//除0以外的數的乘積for(int i=0;i!=arr.length;i++) {if(arr[i]!=0) {all*=arr[i];}else {count++;}}int[] res=new int[arr.length];if(count==0) {for(int i=0;i!=arr.length;i++) {res[i]=all/res[i];}}else if(count==1) {for(int i=0;i!=arr.length;i++) {if(arr[i]==0) {res[i]=all;}}}return res;}

?