今天分享leetcode第5篇文章,也是leetcode第26题—Remove Duplicates from Sorted Array,地址是:https://leetcode.com/problems/remove-duplicates-from-sorted-array/
(本题较为简单,适合练习语法等)
【英文题目】
Given a sorted array nums, remove the duplicates in-place such that each element appear only onceand 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.
Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
【中文题目】
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
【思路】
什么称为in palce(原地)?就是指在原数组上进行操作
如果没有原地这个要求,我们可以新申请一个数组,首先将第0个元素存入新数组中,接着从第1个元素起,只要原数组的当前元素和其前一个元素不同,就将该元素存入新数组中。
但是有了原地这个要求,我们该怎样处理呢?
用一个变量存储不同元素的个数count,那么循环遍历过程中,每遇到一个不同元素,就可以将其存入数组第count个元素位置,最后返回count即可。
在实现过程中,需要注意:数组可能没有元素!
【代码】
python版本
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = 1
length = len(nums)
# 数组可能没有元素
# 元素个数为1,也可直接返回
if length < 2:
return length
for i in range(1, length):
if nums[i] != nums[i-1]:
nums[count] = nums[i]
count += 1
return count
C++版本
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int count = 1;
// 数组可能没有元素
// 元素个数为1,也可直接返回
if(nums.size() < 2)
return nums.size();
for(int i=1; i < nums.size(); i++){
if(nums[i] != nums[i-1]){
nums[count] = nums[i];
count++;
}
}
return count;
}
};