题目描述
-
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
-
现给出一个整型数组nums，他是非递减的顺序，清除重复的元素，使得每一个元素仅仅出现一次。元素之间的相对关系应该被以相同的顺序进行保存。
-
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
-
既然在某些语言中不能改变的数组的长度，你必须使得结果出现在arrays的首部分。更加准确的说是，将所有的重复元素清楚之后，如果有k个元素，那么原来数组的前k个元素必须包含最终的结果。除了链表的前k个元素，无论你丢弃那个都无所谓。
-
Return k after placing the final result in the first k slots of nums.
-
在将最终结果的k个元素放到数组的前k个位置时，返回k值
-
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
-
不能再申请另外一个数组的空间，你必须通过调整和改变输入的数组，而且只能使用O（1）的空间
-
Custom Judge:
-
The judge will test your solution with the following code:
-
判定程序将会使用如下的代码判定你的程序
-
int[] nums = […]; // Input array
-
int[] expectedNums = […]; // The expected answer with correct length
-
int k = removeDuplicates(nums); // Calls your implementation
-
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
-
-
If all assertions pass, then your solution will be accepted.
-
如果所有的断言都通过了，那么最终的结果就会被接收。
-
测试样例
-
Example 1:
- Input: nums = [1,1,2]
- Output: 2, nums = [1,2,_]
- Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores). - 解释：你的函数应该返回k=2，并且前两个元素相应的应该是1和2.再返回的k个元素之后，剩下的元素任意变化都没有任何影响，因此他们是下划线。
-
Example 2:
- Input: nums = [0,0,1,1,1,2,2,3,3,4]
- Output: 5, nums = [0,1,2,3,4,,,,,_]
- Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).- 解释：你的函数应该返回k=5，并且前两个元素相应的应该是1、2、3、4和5.再返回的k个元素之后，剩下的元素任意变化都没有任何影响，因此他们是下划线。
-
Constraints:
- 0 <= nums.length <= 3 * 104
- -100 <= nums[i] <= 100
- nums is sorted in non-decreasing order.
思路分析
- 两个指针进行遍历，相同就改变，不同就不改变。
实现源码
class Solution {
public:
/*
* 描述：nums是要修改的vector数组
* 返回：k是不同的元素
* 注意：传入的是引用，会对原来的数组进行修改
*/
int removeDuplicates(vector<int>& nums) {
//仅有一个元素，直接返回
if(nums.size() <= 1)
return nums.size();
//两个指针用来遍历
int start = 0;
int result =1;
for (int i = 1; i < nums.size(); ++i) {
if(nums.at(i) == nums.at(start)){
nums.at(i) = -99999;
}else{
nums.at(++start) = nums.at(i);
result ++;
}
}
return result;
}
};
事故现场
第一次提交
分析与总结
- 这是一个套题，继续往下看