数组

二维数组查找
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

分析数组的形状，查找应该从左下角（或者右上角开始）

• 如果arr[i][j] >target，i--;
• 如果arr[i][j]<target,j++;
• 列表内容如果arr[i][j]<target,j++;
• 如果相等则返回

比较完之后如果都不相等，则数组说明不包含target
注意：i=arr.length-1; 判断条件里面i>=0;

public class Solution {
    public boolean Find(int target, int [][] array) {
        int i = array.length;
        int j=0;
        while(j<array[0].length&&i>0){
            if(array[i][j]<target){
                j++;
            }
            else if(array[i][j]>target){
                i--;
            }
            else if(target==array[i][j]){
                return true;
            }
        }
        return false;
    }
}

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

public class Solution {
    //    这里要特别注意~返回任意重复的一个，赋值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) {
        int i=0;
        while(i<length){
            while(i!=numbers[i]){
                if(numbers[i]==numbers[numbers[i]]){
                    duplication[0]=numbers[0];
                    return true;
                }
                int temp = numbers[i];
                numbers[i]=numbers[temp];
                numbers[temp] = temp;
            }
            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]。不能使用除法。

剑指offer
分成两部分计算，先计算下三角，然后再计算上三角部分。

public class Solution {
    public int[] multiply(int[] A) {
        int length = A.length;
        int[] B = new int[length];
        if(length != 0 ){
            B[0] = 1;
            //计算下三角连乘
            for(int i = 1; i < length; i++){
                B[i] = B[i-1] * A[i-1];
            }
            int temp = 1;
            //计算上三角
            for(int j = length-2; j >= 0; j--){
                temp *= A[j+1];
                B[j] *= temp;
            }
        }
        return B;
    }
}

数组中出现次数超过一半的数据

遍历数组的时候保存两个值，一是数组中的数字，一是次数。当我们遍历到下一个数字时，如果和之前保存的数字相等，次数+1；反之次数-1；次数=0时，则需要保存数字，并把次数设为1.
最好需要再遍历一次数组检查一下最后保存的数字出现次数是否超过一半。

/**
 * @ author:mian
 * @ DATA:2018/5/17 8:12
 * 数组中出现次数超过一半的数据
 */
public class 数组次数超过一半 {
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int res = array[0];
        int times = 1;
        for (int i = 1; i < array.length; i++) {
            if (times == 0) {
                res = array[i];
                times = 1;
            } else if (array[i] == res) {
                times++;
            } else {
                times--;
            }
        }
        //检查
        if(!idHalf(res,array)){
            return 0;
        }
        return res;
    }
    public boolean idHalf(int number,int[] array){
        int times=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==number)
                times++;
        }
        if(times>array.length/2){
            return true;
        }
        return false;

    }
}

连续子数组的最大和

可以用动态规划的方法求解

/**
 * @ 方法1
 * @ DATA:2018/5/17 8:37
 */
public class 连续子数组的最大和 {
    public static  int FindGreatestSumOfSubArray(int[] array) {
        //可以定义为0的原因是，当sum<=0的时候，会给对其重新赋值。
        int sum=0;

        int max=0x80000000;//int 类型的最小数字。
        for(int i=0;i<array.length;i++){
            if(sum<=0){
                sum=array[i];
            }
            else sum+=array[i];

            if(max<sum)//需要把比较写在后面，否则会报错。因为数据这种可能有负数
                max=sum;
        }
        return max;
    }

    public static void main(String[] args) {
        int[] array ={ 6,-3,-2,7,-15,1,2,2};
        int res = FindGreatestSumOfSubArray(array);
        System.out.println(res);
    }
}