3 數(shù)組中重復(fù)的數(shù)字 *
首先看到有要求復(fù)雜度為 O(N) + O(1)
首先要注意這個(gè)數(shù)組特殊，值都是1-n之間亚情，然后算法比較難想到巫湘，怎么講特別繞
解題思路娄猫，以(2, 3, 1, 0, 2, 5) 為例，先把數(shù)組第一個(gè)值2跟自己的下標(biāo)0比較不相等外冀，那么2與1相比較（1的下標(biāo)是2）寡键，兩者不相等然后交換位置，變成了1 3 2 0 2 5雪隧。
然后比較1與自己的下標(biāo)0不相等西轩，那么1與3比較（3的下標(biāo)是1）师崎，不相等交換位置變成3,1,2,0,2,5
然后3與自己的下標(biāo)0 不相等岛啸，那么3根0比較（0的下標(biāo)是3），不相等于是交換成0,1,2,3,2,5录语。
再次比較0 根 0的下標(biāo)發(fā)現(xiàn)相等庄拇，比較1根1的下標(biāo)也相等注服，同理 2 3都相等，第五個(gè)下標(biāo)是2不相等丛忆，而此時(shí)下標(biāo)2 的地方已經(jīng)存在2了祠汇，那么此時(shí)就找到重復(fù)值了
public static int duplicatenum(int[] arr) {
if(arr==null) return -1;
for(int i=0;i<arr.length;i++) {
while(arr[i] != i) {
if(arr[i]==arr[arr[i]]) {
System.out.println("i is:"+arr[i]);
return i;
}
swap(arr,arr[i],arr[arr[i]]);
}
}
return -1;
}
public static void swap(int[] arr,int start,int end) {
int temp=0;
temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
- 二維數(shù)組中的查找
算法印象很深比較簡(jiǎn)單了
public static boolean find(int target,int[][] arr) {
if(arr==null) return false;
int c = arr.length-1;
int r = 0;
while(c<arr[0].length && r >=0) {
if(arr[r][c] == target) {
System.out.println("i is:"+target);
return true;
} else if(arr[r][c] > target) {
c--;
} else {
r++;
}
}
return false;
}
