题目描述:
给你一个数组
nums
和一个值val
,你需要原地
移除所有数值等于val
的元素,并返回移除后数组的新长度length
。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并
原地
修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
标签:数组、首尾指针
建立模型:
val
时,(交换首尾指针的值,尾指针向左移动)时间复杂度:O(N)
代码实现:
# Python实现
def remove_element(nums: List[int], val: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
if nums[left] == val:
nums[left], nums[right] = nums[right], nums[left]
right -= 1
else:
left += 1
# 由于while循环的条件设置为 i<=j, 所以最后 i 的值始终等于 len(新数组)
return left
/* Java实现 */
public int remove_element(int[] nums, int val) {
int left = 0, right = nums.length - 1;
while (left <= right) {
if (nums[left] == val) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
right -= 1;
}
else {
left += 1;
}
}
return left;
}
题目描述:
给你一个 升序排列的数组
nums
,请你原地
删除重复出现的元素,使每个元素只出现一次
,返回删除后数组的新长度length
。元素的相对顺序
应该保持 一致 。由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
标签:数组、快慢指针
建立模型:
nums[fast] != nums[fast - 1]
,将快指针指向的当前元素插入慢指针指向的位置,快、慢指针同时向右移动nums[fast] == nums[fast - 1]
,只向右移动快指针fast == nums.length
时间复杂度:O(N)
代码实现:
# Python实现
def remove_duplicates(nums:List[int]) -> int:
if not nums:
return 0
slow, fast = 1, 1
while fast < len(nums):
if nums[fast] != nums[fast - 1]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
/* Java实现 */
int remove_duplicates(int[] nums) {
if (nums.length == 0){
return 0;
}
int slow = 1, fast = 1;
while (fast < nums.length) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
slow += 1;
}
fast += 1;
}
return slow;
}
题目描述:
给定一个数组
nums
,编写一个函数将所有0
移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。
标签:数组、快慢指针
时间复杂度:O(N)
建立模型:
nums[right] != 0
,则交换快慢指针的值,快慢指针同时右移nums[right] == 0
,则只向右移动快指针right == nums.length
代码实现:
# Python实现
def move_zeroes(self, nums: List[int]) -> None:
left, right = 0, 0
while right < len(nums):
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
return None
/* Java实现 */
public void move_zeroes(int[] nums) {
int left = 0, right = 0;
while (right < nums.length) {
if (nums[right] != 0) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left += 1;
}
right += 1
}
return;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章