剑指offer-JavaScript版本实现（1）--数组部分

以你之姓@ 2023-07-07 03:43 14阅读 0赞

自己总结下刷完剑指offer，使用js的实现等。

# 一、二维数组的查找 #

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

方法一: 把每一行看成有序递增的数组，利用二分查找，通过遍历每一行去得到是否含有该整数， 时间复杂度： O(n\*logn)

function Find(target, array)
    {
        // write code here
        for(let i = 0; i < array.length;i++){
            if(binarySearch(target,array[i])){
                return true;
            }
        }
        return false;
    }
     
    function binarySearch(target,arr){
        let low = 0;
        let high = arr.length - 1;
        while(low <= high){
            let mid = parseInt((low + high) / 2);
            if(target < arr[mid]){
                high = mid - 1;
            }else if(target > arr[mid]){
                low = mid + 1;
            }else if(target == arr[mid]) {
                return true;
            }else return false;
            
        }
        return false;
    }

方法二： 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增。 因此从左下角开始查找，当要查找的数字比左下角数字的时候，向右移动； 当要查找的数字比左下角数字小时，向上移动。 时间复杂度: O(行高 + 列宽) ， 空间复杂度： O(1)

function Find(target, array)
    {
        // write code here
        let row = array.length;
        let col = array[0].length;
        if (row == 0 || col == 0) return false;
        let i = row - 1;
        let j = 0;
        while(i >= 0 && j < col){
           if (target < array[i][j]) {
                i--;
                continue;
            } else if (target > array[i][j]) {
                j++;
                continue;
            } else {
                return true;
            }
        }
        return false;
    }

方法三: 一行代码，实用型

function Find(target, array) {
        return array.some(arr => arr.some(e => e === target))
    }

# 二、 重复的数字 #

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

方法一： 利用hash，也就是js里面的\{\}；

function duplicate(numbers, duplication)
    {
        // write code here
        //这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
        //函数返回True/False
        var len = numbers.length;
        var obj = {};
        for(var i = 0; i < len; i++) {
            if(numbers[i] in obj) {
                duplication[0] = numbers[i];
                return true;
            } else {
                obj[numbers[i]] = 1;
            }
        }
        return false;
    }

方法二：

1.  把当前序列当成是一个下标和下标对应值是相同的数组；
2.  遍历数组，判断当前位的值和下标是否相等： 2.1. 若相等，则遍历下一位； 2.2. 若不等，则将当前位置i上的元素和a\[i\]位置上的元素比较：若它们相等，则成功; 若不等，则将它们两交换。换完之后a\[i\]位置上的值和它的下标是对应的，但i位置上的元素和下标并不一定对应；
3.  重复2.2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2.

时间复杂度O（n）， 空间复杂度O（1）

function duplicate(numbers, duplication)
    {
        // write code here
        //这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
        //函数返回True/False
       let len = numbers.length;
       if (numbers == null || len <= 0) return false;
        for(let i = 0; i < len; i++) {
            while(numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                let temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        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\]。不能使用除法。（注意：规定B\[0\]和B\[n-1\] = 1）

B\[i\]的值可以看作下图的矩阵中每行的乘积。 先算下三角中的连乘，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

![format_png][]

function multiply(a)
    {
        // write code here
        var len = a.length;
        var b = [];
        if (len != 0) {
            b[0] = 1;
            
            for(var i = 1; i < len; i++) {
                b[i] = b[i-1] * a[i-1];
            }
            var temp = 1;
            
            for(var j = len - 2; j >= 0; j--) {
                temp *= a[j+1];
                b[j] *= temp;
            }
        }
        return b;
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAyMC8yLzE3LzE3MDUzZDUxNTYxMTRiOWY?x-oss-process=image/format,png

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer】1.二维数组查找

/ 题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的

清疚/ 2023年10月17日 18:38/ 0 赞/ 170 阅读

相关剑指offer 数组

关于数组的几点知识： 1：数组的时间效率很高：可根据下标在O(1)时间内读写任何元素。数组空间效率较差：即使是只存储一个数据，也需要为数组分配预定大小的内存，产生一

Myth丶恋晨/ 2023年10月17日 16:29/ 0 赞/ 114 阅读

相关剑指offer-JavaScript版本实现（3）--二叉树部分

一、二叉树的下一个结点题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的

比眉伴天荒/ 2023年07月07日 11:21/ 0 赞/ 23 阅读

相关剑指offer-JavaScript版本实现（1）--数组部分

自己总结下刷完剑指offer，使用js的实现等。一、二维数组的查找题目描述: 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，

以你之姓@/ 2023年07月07日 03:43/ 0 赞/ 15 阅读

相关剑指offer-JavaScript版本实现（2）--链表部分

题目一、从头到尾打印链表题目描述：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。创建一个空数组，将每个节点存放在数组中；将当前节点放到数组

柔光的暖阳◎/ 2023年07月07日 03:43/ 0 赞/ 13 阅读

相关《剑指offer》：数组部分

一、数组中重复的数字题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出

墨蓝/ 2023年07月04日 15:51/ 0 赞/ 215 阅读

相关剑指 offer (1) -- 数组篇

算法难，难如上青天，但是难也得静下心来慢慢学习，并总结归纳。所以将剑指 `offer` 中的题目按照类别进行了归纳，这是第一篇--数组篇。当然，如果各位大佬发现程序有什么 `b

蔚落/ 2022年10月01日 06:46/ 0 赞/ 260 阅读

相关剑指offer python版本

1. 二叉树的镜像 2. 链表中环的入口结点 3. 删除链表中重复的结点 4. 从尾到头打印链表 5. 斐波那契数列 6. 跳台阶 7. 变态跳台阶 8. 矩形

左手的ㄟ右手/ 2022年05月20日 03:54/ 0 赞/ 292 阅读

相关剑指offer全集python（1/3）第一大部分

目录 2.使用python实现单例模式 3.二维数组中数的搜索 4.替换空格 5.从尾到头打印单链表值 6.根据前序，中序构造二叉树 7.使用2个栈实现队列 8.

ゞ浴缸里的玫瑰/ 2022年03月02日 06:54/ 0 赞/ 259 阅读

相关剑指offer（1）——C++实现二维数组中的查找

/二维数组查找/ include<iostream> include<vector> using namespace std; clas

古城微笑少年丶/ 2021年11月09日 04:10/ 0 赞/ 199 阅读