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
的长度