代码随想录01 数组

数组基础

数组是存放在连续内存空间上的相同类型数据的集合，可以方便的通过下标索引的方式获取到下标对应的数据。

array

JavaScript 数组基础

toString()方法，将数组转换为逗号分隔的字符串，在需要时，toString()会自动调用。

let fruits = ["Banana", "Orange", "Apple", "Mango"];
console.log(fruits.toString())

// Output: Banana,Orange,Apple,Mango

// document.getElementById("demo").innerHTML = fruits.toString(); 
// document.getElementById("demo").innerHTML = fruits; 
// 两种方式等价

join()方法，将数组中元素用制定分隔符连接起来，输出字符串

let fruits = ["Banana", "Orange", "Apple", "Mango"];
console.log(fruits.join(" * "))

// Output: Banana * Orange * Apple * Mango

pop()方法删除最后一个元素，并返回该值；

push()方法在最后添加一个元素，返回数组长度;

shift()方法在删除第一个元素，并返回该值;

unshift()方法在开头添加一个元素，返回数组长度;

// pop()
var fruits = ["Banana", "Orange", "Apple", "Mango"];
var x = fruits.pop();      
// x 的值是 "Mango"
// fruits = ["Banana", "Orange", "Apple"]

// push()
var fruits = ["Banana", "Orange", "Apple", "Mango"];
var x =  fruits.push("Kiwi");   
//  x 的值是 5       
//  fruits = ["Banana", "Orange", "Apple", "Mango", "Kiwi"]

// shift()
var fruits = ["Banana", "Orange", "Apple", "Mango"];
var x = fruits.pop();    
// x 的值是 "Banana"
// fruits = ["Orange", "Apple", "Mango"]

// unshift()
var fruits = ["Banana", "Orange", "Apple", "Mango"];
var x =  fruits.push("Kiwi");   
//  x 的值是 5       
//  fruits = ["Kiwi", "Banana", "Orange", "Apple", "Mango"]

用索引号修改元素

1
2
3

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits[0] = "Kiwi";        
// 把 fruits 的第一个元素改为 "Kiwi"

通过length属性获取数组长度

1
2
3

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits[fruits.length] = "Kiwi";          
// 向 fruits 追加 "Kiwi"

通过delete运算符删除元素（会留下 undefined 空洞）

1
2
3

var fruits = ["Banana", "Orange", "Apple", "Mango"];
delete fruits[0];           
// 把 fruits 中的首个元素改为 undefined

splice()方法为数组添加新元素，第一个参数定义添加新元素的位置（拼接），第二个参数定义应删除多少元素，其余参数（“Lemon”，“Kiwi”）定义要添加的新元素。返回删除项组成的数组。

var fruits = ["Banana", "Orange", "Apple", "Mango"];
let removed = fruits.splice(2, 2, "Lemon", "Kiwi");
// fruits = ["Banana", "Orange", "Lemon", "Kiwi"]
// removed = ["Apple", "Mango"]

concat方法合并数组（原数组不变），返回一个新的数组。可以有多个参数，也能以值作为参数。

var arr1 = ["Cecilie", "Lone"];
var arr2 = ["Emil", "Tobias", "Linus"];
var arr3 = ["Robin", "Morgan"];
var myChildren = arr1.concat(arr2, arr3);   
// 将arr1、arr2 与 arr3 连接在一起
// myChildren = ["Cecilie", "Lone", "Emil", "Tobias", "Linus", "Robin", "Morgan"]

slice()方法从原数组中截取一段数组，而不改变原数组，第一个参数表示起始位置（包括），第二个表示结束位置（不包括），如果第二个参数省略，切出所有剩余部分；

1 2	`var fruits = ["Banana", "Orange", "Lemon", "Apple", "Mango"]; var citrus = fruits.slice(1, 3);`

JavaScript 数组排序

sort()方法，最强大的数组方法之一

默认情况下，按照字符串顺序排序

1
2
3

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.sort(); 
// Apple,Banana,Mango,Orange

而对于数值类型，需要添加比较函数，比较函数传入两个参数，并根据返回值的正负，判断顺序

如 40 和 100，传入后，100-40=60 > 0，所以40 比 100 更大

1
2
3

var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return b - a}); 
// 100,40,25,10,5,1

同样的，也可以利用Math.random()进行随机排序，该方法返回0（包含）到1（不包含）的为随机数，这样就能获得一半概率a>b，一半概率a<b的情况，进行随机打乱

1 2	`var points = [40, 100, 1, 5, 25, 10]; points.sort(function(a, b){return 0.5 - Math.random()});`

尽管对象有多种不同类型数据，也可以使用sort()方法的比较函数排序

var cars = [
{type:"Volvo", year:2016},
{type:"Saab", year:2001},
{type:"BMW", year:2010}];
cars.sort(function(a, b){return a.year - b.year});

reverse()方法，将数组倒序

1
2
3

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.sort();            // 对 fruits 中的元素进行排序
fruits.reverse();         // Orange,Mango,Banana,Apple

如果只是要找到最大/最小值，无需对整个数组排序，可以使用Math.max()或Math.min()方法

// Math.max.apply([1, 2, 3]) 等于 Math.max(1, 2, 3)。
function myArrayMax(arr) {
    return Math.max.apply(null, arr);
}

// Math.min.apply([1, 2, 3]) 等于 Math.min(1, 2, 3)。
function myArrayMin(arr) {
    return Math.min.apply(null, arr);
}

JavaScript 数组迭代

Array.forEach()对每个数组元素调用一次回调，接受 3 个参数：项目值、项目索引、数组本身
Array.map()方法通过对每个数组元素执行函数来创建新数组，不会对没有值的数组元素执行函数，也不会更改原始数组
Array.filter()方法创建一个包含通过测试的数组元素的新数组
Array.reduce()方法在每个数组元素上运行函数，以生成（减少它）单个值,在数组中从左到右工作(reduceRight()方法则从右到左工作) ，不会减少原始数组。

reduce()方法的回调函数接受四个参数，一个初始值（初始值也可以放在回调函数后，作为第二个大参数传入），和项目值、项目索引、数组本身

Array.every()检验数组中的所有值是否均满足函数要求，Array.some()则只检验是否有值满足（至少一个）
Array.find()找到第一个满足要求的数组元素的值，Array.findIndex()则返回索引
Array.indexOf()从头部开始搜索元素位置，Array.lastIndexOf()从尾部开始搜索

数组题目

LeetCode 704 二分查找（二分法）

力扣题目链接

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

思路

使用二分法的前提是有序数组，且无重复元素，在元素重复时，二分法得到的元素下标可能不唯一；

设置 left, mid, right 三个指针，每次都用中间位置作比较：

如果比目标大，就在左半边（升序情况）找，将 right更新为 mid - 1;

如果比目标小，就在右半边找，将 left 更新为 mid + 1;

如果相等，直接返回，

到最后，left, mid, right 三个值相等，再找就会使得left > right，跳出循环，返回 -1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    // right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
    let mid, left = 0, right = nums.length - 1;
    // 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
    while (left <= right) {
        // 位运算 + 防止大数溢出
        mid = left + ((right - left) >> 1);
        // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1；如果右边界更新为mid，那中间数还在下次查找范围内
        if (nums[mid] > target) {
            right = mid - 1;  // 去左面闭区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右面闭区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};

LeetCode 27 移除元素

力扣题目链接

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

var removeElement = function(nums, val) {
    let k = 0;
    for (let i = 0; i < nums.length; i++){
        if (nums[i] != val) {
            nums[k++] = nums[i]
        }
    }
    return k
};

LeetCode 977 有序数组的平方（双指针）

力扣题目链接

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

var sortedSquares = function (nums) {
    nums.map( item => item*item)
    let start = 0, end = nums.length-1
    let result = new Array(nums.length).fill(0)
    
    let left = nums[start] * nums[start]
    let right = nums[end] * nums[end]
    for (let i = nums.length - 1; i >= 0 ; i--) {
        if (left >= right) {
            result[i] = left
            start++
            left =  nums[start] * nums[start]
        } else {
            result[i] = right
            end--
            right =  nums[end] * nums[end]
        }
    }
    return result
};

Leetcode 209 长度最小的子数组（滑动窗口）

力扣题目链接(opens new window)

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

var minSubArrayLen = function (target, nums) {
    let start = 0;
    let sum = 0;
    let result = nums.length+1;
    
    for (let i = start; i < nums.length; i++){
        sum+=nums[i]
        while (sum >= target) {
            if (i - start + 1 < result)
            result = i - start + 1
            sum -= nums[start]
            start++
        }
    }
    if (result == nums.length + 1) {
        return 0
    } else {
        return result
    }
};

Leetcode 59 螺旋矩阵II

力扣题目链接(opens new window)

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

var generateMatrix = function(n) {
    let item = 1;
    let a = new Array(n).fill(0).map(()=> new Array(n).fill(0))

    // 画几圈？
    for ( let i = 0; i <= Math.floor(n/2); i++ ) {
        if (i == Math.floor(n/2) && n % 2 == 1) {
            a[i][i] = n*n
            break;
        }
        
        // 画四条边

        // 上边
        for (let t = i; t < n - 1 - i; t++) {
            console.log(item)
            a[i][t] = item
            a[t][n-1-i] = item + (n - 1 - 2*i)
            a[n-1-i][n-1-t] = item + 2*(n - 1 - 2*i)
            a[n-1-t][i] = item + 3*(n - 1 - 2*i)
            item++
        }
        
        if (1+i < n-1){
            
        item = a[1+i][i]
        item++
        }
    }
    return a
};

Note

#Algorithm #Array

代码随想录01 数组

https://username.github.io/2024/07/01/代码随想录01-数组/

作者

ZhuoRan-Takuzen

发布于

2024年7月1日

许可协议

代码随想录02 链表上一篇

Apache-Jena 学习笔记下一篇

代码随想录01 数组

数组基础

JavaScript 数组基础

JavaScript 数组排序

JavaScript 数组迭代

数组题目

LeetCode 704 二分查找 （二分法）

思路

LeetCode 27 移除元素

LeetCode 977 有序数组的平方 （双指针）

Leetcode 209 长度最小的子数组 （滑动窗口）

Leetcode 59 螺旋矩阵II

LeetCode 704 二分查找（二分法）

LeetCode 977 有序数组的平方（双指针）

Leetcode 209 长度最小的子数组（滑动窗口）