第81天。
今天的题目是Remove Element:
Given an array and a value, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Example:
Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
简单的我们可以遍历数组,然后找到和val
相同的元素,然后删除,但是这样对于多个相同的元素效率不高,所以我们先不删除元素,而是把他移动到最后面去,知道遍历完才删除。
1int removeElement(vector<int>& nums, int val) {2 int last = nums.size();3 for(int i = 0;i < last;i++) {4 if (nums[i] == val) swap(nums[--last],nums[i--]);5 }6 nums.erase(nums.begin() + last,nums.end());7 return nums.size();8}
dicuss
中另一个方法也很精妙:
1int removeElement(int A[], int n, int elem) {2 int begin=0;3 for(int i=0;i<n;i++) if(A[i]!=elem) A[begin++]=A[i];4 return begin;5}