数组

作者: 安于此生__ | 来源:发表于2018-05-11 09:28 被阅读0次

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

分析数组的形状,查找应该从左下角(或者右上角开始)

  • 如果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);
    }
}

相关文章

  • 数组

    数组数组数组数组数组数组数组数组数组

  • JavaScript - 5.数组<增删改查>

    数组 Array 数组 - 增 数组 - 删 / 改 数组 - 查 数组 - 自动 toString() 数组 -...

  • PHP数组使用

    数组定义 数组增、删、改 数组查询 数组排序 数组合并、分割 数组比较、去重复 数组长度 数组遍历 数组转换 其他...

  • 》》》PHP初入---(三)

    数组定义 1.索引数组:数组下标是整型的 声明数组: 访问数组: count(数组)--获取数组长度 查看数组所有...

  • JavaScript中数组的常用操作

    数组的遍历 数组的映射 数组的简化 数组的连接 获取数组的片段 数组的拷贝 查找数组 数组去重

  • JavaSE之数组

    六、数组 目录:数组概述、数组声明创建、数组使用、多维数组、Array类、稀疏数组 1.什么是数组 数组的定义:数...

  • Shell数组、关联数组

    数组 定义数组 获取数组 关联数组 定义关联数组 获取关联数组

  • 学习Java第五天

    数组是多个数据的集合 数组的语法 数组元素类型【】 数组名; 多维数组: 数组元素类型【】【】 数组名; 多维数组...

  • php基础精粹

    PHP php数组 php数组之索引数组初始化 PHP数组之索引数组赋值 PHP数组之访问索引数组内容 PHP数组...

  • C语言的惯用集

    数组部分 数组部分 清空数组a 把数据读进数组a 对数组a求和

网友评论

      本文标题:数组

      本文链接:https://www.haomeiwen.com/subject/qfgxdftx.html