3 数组中重复的数字 *
首先看到有要求复杂度为 O(N) + O(1)
首先要注意这个数组特殊，值都是1-n之间，然后算法比较难想到，怎么讲特别绕
解题思路，以(2, 3, 1, 0, 2, 5) 为例，先把数组第一个值2跟自己的下标0比较不相等，那么2与1相比较（1的下标是2），两者不相等然后交换位置，变成了1 3 2 0 2 5。
然后比较1与自己的下标0不相等，那么1与3比较（3的下标是1），不相等交换位置变成3,1,2,0,2,5
然后3与自己的下标0 不相等，那么3根0比较（0的下标是3），不相等于是交换成0,1,2,3,2,5。
再次比较0 根 0的下标发现相等，比较1根1的下标也相等，同理 2 3都相等，第五个下标是2不相等，而此时下标2 的地方已经存在2了，那么此时就找到重复值了
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;
}
- 二维数组中的查找
算法印象很深比较简单了
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;
}
