题一：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
分析：二维数组左小右大，上下下大，那么左上角的是最小值，右下角是最大值。如果两次循环遍历查找，查找顺序是从左上找到右下，复杂度为O(N^2)；如果从左下开始查找，则只需查找上三角区；如果从右上角查询，则只需查找下三角区；复杂度为O（M+N）
1 public class Solution { 2 public boolean Find(int target, int [][] array) { 3 int rowLen = array.length;//行数 4 int colLen = array[0].length;//列数 5 int row=rowLen-1,col=0; 6 while(row>=0&&col<colLen){ 7 if(target<array[row][col]){ 8 row--;//向上 9 }else if(target>array[row][col]){ 10 col++;//向右 11 }else{ 12 return true; 13 } 14 } 15 return false; 16 } 17 }
题二：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
1.暴力破解（O(N^2)）
1 public class Solution { 2 public boolean duplicate(int numbers[],int length,int [] duplication) { 3 for(int i=0;i<length;i++){ 4 int temp = numbers[i]; 5 for(int j=i+1;j<length;j++){ 6 if(temp==numbers[j]){ 7 duplication[0]=numbers[j]; 8 return true; 9 } 10 } 11 } 12 return false; 13 } 14 }
2.根据题意，长度为n的数组内的数字范围为0~n-1。如果没有重复的数字，那么排序后的数据是0~n-1，即numbers[i]=i 。
--->扫描整个数组，数字m对应的坐标为i，
A.如果m=i，则i++遍历下一个数字；
B.如果m！=i，那么比较m和numbers[m]是否相等；
a.如果m！=numbers[m]，则交换m和numbers[m]；并且从当前位置再次遍历；
b.如果m=numbers[m]，则说明有重复值；
1 public class Solution { 2 public boolean duplicate(int numbers[],int length,int [] duplication) { 3 int index=0; 4 while(index<length){ 5 if(index==numbers[index]){ 6 index++; 7 }else{ 8 int temp = numbers[index]; 9 if(temp==numbers[temp]){ 10 duplication[0]=temp; 11 return true; 12 }else{ 13 numbers[index] = numbers[temp]; 14 numbers[temp] = temp; 15 } 16 } 17 } 18 return false; 19 } 20 }
题二：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
1.暴力解决O(N^2)
1 import java.util.ArrayList; 2 public class Solution { 3 public int[] multiply(int[] A) { 4 int[] B = new int[A.length]; 5 for(int i=0;i<A.length;i++){ 6 int value=1; 7 for(int j=0;j<A.length;j++){ 8 if(j!=i){ 9 value=value*A[j]; 10 } 11 } 12 B[i]=value; 13 } 14 return B; 15 } 16 }
2.将A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]分成两个部分，第一次遍历，数组B存入A[0]*A[1]*...*A[i-1]。第二次遍历存入A[i+1]*...*A[n-1]；使用相乘B[i] =B[i]*value;衔接；O(N)
1 import java.util.ArrayList; 2 public class Solution { 3 public int[] multiply(int[] A) { 4 int[] B = new int[A.length]; 5 int value = 1; 6 for(int i=0;i<A.length;i++){ 7 B[i] = value; 8 //从前往后遍历，初始B[0]=value=1； 9 //value=A[0]*A[1]*...*A[i-1] 10 value = value*A[i]; 11 } 12 value = 1; 13 for(int i=A.length-1;i>=0;i--){ 14 B[i] =B[i]*value;//更新B[i] 15 //value=A[i+1]*A[i+2]*..*A[n] 16 value = value*A[i]; 17 } 18 return B; 19 } 20 }
原文：https://www.cnblogs.com/qmillet/p/11942269.html