分享,进步,自足

标签 算法 下的文章

13/2
2019

二维数组中的查找

题目描述

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

例如:

输入:16, [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]
输出:false


一般情况下我们可以使用两个for循环进行遍历,代码是这样:

function Find(target, array){
    for(var i = 0;i < array.length;i++){
        for(var j = 0;j < array[i].length;j++){
            if(array[i][j] == target){
                return true;
            }
        }
    }
    return false;
}

但是这样浪费了题目中的信息,题目中说这是一个有序序列,并且子数组的长度相同,并且这样的时间复杂度是O(n^2)。


所以可以考虑其它方式,首先把数组写成二维的样式,如下:

子数组0 子数组1 子数组2 子数组3
1 2 4 6
2 4 7 8
8 9 10 11
9 12 13 15

观察得知从上至下是递增,从左至右也是递增。现在以左下角的数字9作为开始数字,对传入的数字与9相比较,如果比9小则向上移动,如果比9大则向右移动,一直重复就可以找到这个数字。
为什么不从左上角开始呢,因为左上角不管向下还是向右都是递增,这是一个分岔路口,程序不知道应该走哪边,所以选择左下角唯一的。
代码如下:

function Find(target, array) {
    var num1 = array.length;
    var num2 = array[0].length;
    for (var i = 0, j = num2 - 1; i < num1 && j >= 0;) {
        /*
            i代表列,j代表行,初始就为左下角的数字。
            i<num1是列的边界,j>=0是行的边界(子数组边界)
        */
        if (target == array[i][j]) {
            return true;
        }
        if (target > array[i][j]) {
            i++;
            continue;
        }
        if (target < array[i][j]) {
            j--;
            continue;
        }
    }
    return false;
}

当然也有一些其它方法,比如把子数组进行二分法查找,并对每个子数组都这样操作。不过这里就讨论了。

+ MORE

30/1
2019

移除数组中的元素

题目描述

移除数组 arr 中的所有值与 item 相等的元素。不要直接修改数组 arr,结果返回新的数组

示例

输入:
[1, 2, 3, 4, 2], 2

输出:
[1, 3, 4]

个人思路

题目要求需要不直接修改原数组,所以需要复制一个新数组,再使用splice函数删除与item相同的项。
所以我得到的代码如下:

function remove(arr,item){
    var newarr = arr;
    for(var i=0;i<newarr.length;i++){
        if(newarr[i] == item){
            newarr.splice(i,1);
        }
    }
    return newarr;
}

但是实际上这个代码并没有通过测试,经过检查发现了如下的错误:

  1. 数组不是基本数据类型,而是一个引用数据类型或者叫做复杂数据类型,此类型的变量存的不是数据本身,存的是指向堆内存中的地址,直接赋值后实际上newarr和arr是指向同一个数组,不符合题目要求:不直接修改数组arr。
  2. 使用splice函数后,数组的长度会少一,整体内容会向左移,如果数组内有连续相同的元素,会漏掉最后一个元素不能被移除。
    所以修改后的代码如下:
function remove(arr,item){
    var newarr = arr.slice(0);
    for(var i=0;i<newarr.length;i++){
        if(newarr[i] == item){
            newarr.splice(i,1);
            i--;
        }
    }
    return newarr;
}

这样就可以通过测试了。但是实际上方法不止一个,下面给出其它方法:

其它方法

function remove(arr,item){
    var newarr = [];
    for(var i=0;i<arr.length;i++){
        if(arr[i] != item){
            newarr.push(arr[i]);
        }
    }
    return newarr;
}

这个方法和我想的是一类,新建一个新数组,把不同的元素添加进去


function remove(arr,item){
    return arr.filter(function(ele){
         return ele != item;
    })
}

filter()函数是用于筛选数组用的,函数是这样工作的:filter()函数可以接收一个参数,这个参数是一个回调函数,filter函数会把数组中的每个元素作用于回调函数,作用之后如果回调返回值是false就丢弃这个元素,如果是true就保留这个元素,然后依次对数组的每个元素都执行这个操作。
所以上述代码:如果数组元素与item不等就返回true,保留元素;否则返回false,丢弃元素。

+ MORE