LeetCode 27+LeetCode 35 讲解(姊妹篇)

简介: LeetCode 27+LeetCode 35 讲解(姊妹篇)

LeetCode 27


题目


给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。


思路分析


(1)首先可以观察到这是一个去除数组类相同元素的一个算法题,在本题中,我们可以通过for循环加上if匹配对数组进行逐项比较,最终得出想要的结果

(2)再仔细观察这题,我还想到了遍历数组长度,因为在LeetCode 1里面我们遇到过类似的情景,当时是用nums数组的值去跟目标值target作比较从而去重

(3)双指针思想


代码实现


class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}


代码详解


(1)首先定义一个n变量用于存储数组nums的长度

(2)运用双指针的思想,定义左指针left及右指针right,由于左指针较慢,右指针较快,所以采用for循环去遍历右指针,如果右指针中的元素与目标值val不一样,则进行一次赋值操作,将右指针的值赋给左指针,最终返回左指针的长度

(3)题目整体不难,主要参照LeetCode 26的思想去做,很容易就能做出来


LeetCode 35


题目


给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。


思路分析


(1)这一条仍然是一条算法题目,在数组算法的基础上,加上了索引的概念,但是这个无伤大雅,不会影响读者做题

(2)这一题本质上仍然是数组元素匹配与target的问题


代码实现


class Solution {
public int searchInsert(int[] nums, int target) {
    for(int i = 0; i < nums.length;i++){
        if(nums[i] >= target){
            return i;
        }
    }
    return nums.length;
}
}


代码详解


(1)此题方法比较新颖,运用for循环来遍历数组nums的长度

(2)如果数组nums里面的i元素比目标值要大,则返回元素i的值,如果数组nums里面的i元素比目标只要小,则返回数组nums的长度

相关文章
|
6月前
leetcode-827:最大人工岛
leetcode-827:最大人工岛
61 0
|
存储
leetcode:53.最大字序和
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
52 0
LeetCode 354. Russian Doll Envelopes
给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
81 0
LeetCode 354. Russian Doll Envelopes
LeetCode 283. 移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
86 0
leetcode第44题
时间复杂度:text 长度是 T,pattern 长度是 P,那么就是 O(TP)。 空间复杂度:O(TP)。 同样的,和第10题一样,可以优化空间复杂度。
leetcode第44题
|
存储
leetcode第52题
可以发现对于同一条副对角线,row + col 的值是相等的。 对于同一条主对角线,row - col 的值是相等的。 我们同样可以用一个 bool 型数组,来保存当前对角线是否有元素,把它们相加相减的值作为下标。 对于 row - col ,由于出现了负数,所以可以加 1 个 n,由 [ - 3, 3 ] 转换为 [ 1 , 7 ] 。
leetcode第52题
leetcode第54题
在 leetcode 的 solution 和 discuss 看了下,基本就是这个思路了,只是实现上有些不同,怎么用来标记是否走过,当前方向,怎么遍历,实现有些不同,但本质上是一样的。就是充分理解题意,然后模仿遍历的过程。
103 0
leetcode第54题
leetcode第36题
一个 9 * 9 的数独的棋盘。判断已经写入数字的棋盘是不是合法。需要满足下边三点, • 每一行的数字不能重复 • 每一列的数字不能重复 • 9 个 3 * 3 的小棋盘中的数字也不能重复。 只能是 1 - 9 中的数字,不需要考虑数独最后能不能填满
leetcode第36题