数组问题（Java实现）

<一>二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

代码如下：

public class Solution {
    public boolean Find(int target, int [][] array) {
        
        for(int i = 0;i < array.length;i++){
            for(int j = array[0].length - 1;j >=0;j--){
                 if(array[i][j] > target){  //取值和目标整数相比较！
                    j--; 
                 }else if(array[i][j] < target){
                    i++;
                 }else
                    return true;
            }
        }
        return false;
    }
}

 上述的方法通不过测试用例，可能是时间复杂度的原因。

完美代码如下：（从矩阵的左下角开始）

public class Solution {
    public boolean Find(int target, int [][] array) {

        int len = array.length - 1;  //行
        int i = 0;   //列
        while(len >= 0 && i < array[0].length){  //行大于零，列小于数组总长度
            if(array[len][i] > target){  //取值和目标整数相比较！
                len--; 
            }else if(array[len][i] < target){
                i++;
            }else
                return true;
        }
        return false;
    }
}

 完美代码如下：（从矩阵的右上角开始）

public class Solution {
    public boolean Find(int target, int [][] array) {

        int len = 0;  //行
        int i = array[0].length - 1;   //列
        while(len < array.length && i >= 0){  //行大于零，列小于数组总长度
            if(array[len][i] > target){  //取值和目标整数相比较！
                i--; 
            }else if(array[len][i] < target){
                len++;
            }else
                return true;
        }
        return false;
    }
}

 <二>数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

代码如下：

import java.util.HashSet;
public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
    
        if(length <= 0){
            return false;
        }
        HashSet<Integer> se = new HashSet<>();
        for(int i = 0; i < length;i++){
            if(se.contains(numbers[i])){
                duplication[0] = numbers[i];
                return true;
            }else{
                se.add(numbers[i]);
            }
        }
       return false;
    }
}

<三>构建乘积数组

题目描述

给定一个数组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]。不能使用除法。

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {

        int len = A.length;
        int[] B = new int[len];
        
        int res = 1;
        for(int i = 0;i < len;res *= A[i++]){
            B[i] = res;
        }
        res = 1;
        for(int j = len - 1;j >= 0;res *= A[j--]){
            B[j] *= res;
        }
        return B;
    }
}