48°

leetcode27之移除元素

题目描述:

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

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

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

 

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/remove-element

代码实现:

 1 def removeitem(nums, tar):
 2     ans = 0
 3     for num in range(len(nums)):
 4         if nums[num] != tar:
 5             nums[ans] = nums[num]
 6             ans += 1
 7         else:
 8             continue
 9 
10     return ans
11 
12 
13 print("---------------测试removeitem()-------------")
14 nums = [3, 3, 3, 3, 3]
15 target = 2
16 res = removeitem(nums, target)
17 print("res=", res)
18 
19 
20 def removeitem1(nums, tar):
21     '''
22 
23     :param nums:
24     :param tar:
25     :return:
26     '''
27     for i in range(len(nums) - 1, -1, -1):
28         if (nums[i] == tar):
29             nums.pop(i)
30 
31     return len(nums)
32 
33 
34 print("---------------测试removeitem1()-------------")
35 nums = [3, 3, 3, 3, 3]
36 target = 2
37 res = removeitem1(nums, target)
38 print("res=", res)
39 
40 
41 def removeitem2(nums, tar):
42     '''
43 
44     :param nums:
45     :param tar:
46     :return:
47     '''
48     l=len(nums)
49     for i in range(l):
50         if (nums[i] != tar):
51             nums.append(nums[i])
52             # nums.pop(i)
53     del nums[:l]
54     return len(nums)
55 
56 print("---------------测试removeitem2()-------------")
57 nums = [3, 3, 3, 3, 3]
58 target = 2
59 res = removeitem2(nums, target)
60 print("res=", res)

输出:

---------------测试removeitem()-------------
res= 5
---------------测试removeitem1()-------------
res= 5
---------------测试removeitem2()-------------
res= 5

总结:1、原地移除元素,考虑使用双指针。方法一正是采用了类似双指针策略来实现。遍历整个数组,若该元素与目标元素相等,跳过继续循环,若不想等,执行nums[ans]=nums[num]操作,ans+=1。返回ans即为最终数组长度。

2、方法二思路很值得借鉴,考虑从数组末尾开始遍历,如果相等,弹出该元素;如果不相等,继续循环。返回为len(nums)

3、方法三追加元素+删除数组方法。从头开始遍历数组,如果相等,跳过继续循环;如果不等,在数组末尾追加该元素。循环结束后删除原有长度数组,返回len(nums)。该方法依然满足O(1)复杂度要求

本文转载自博客园,原文链接:https://www.cnblogs.com/rounie/p/13169905.html

全部评论: 0

    我有话说: