leetcode27之移除元素

rounie 2020-06-20 原文

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)复杂度要求