LeetCode 解题记录

ARRAY

27. Remove Element [EASY]

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 in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.
【题目大意】:输入一个数组和某个值,剔除数组中与该值相同的元素(只能在该数组中操作)

解题思路

设置一个int变量replace_post用来记录被剔除的元素的位置,将未被剔除的元素放到该位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int replace_post=0;
for (int j=0;j<nums.size();j++){
if (nums[j]!=val){
nums[replace_post]=nums[j];
replace_post++;
}
}
return i;
}
};

运行结果

1
2
输入 [3,2,2,3],3
输出 [2,2],2

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
题目大意: 剔除有序数组中相同的元素

题目不难,直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size()==0){
return 0;
}
int index=0;
for (int i=1;i<nums.size();i++){
if (nums[index]!=nums[i]){
nums[++index]=nums[i];
}
}
return index+1;
}
};

80. Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3.

题目大意: 对于一个有序数组,最多允许两个相同元素,请将不满足要求的元素剔除。并返回数组长度。

普通解法 [16ms]

设置index(‘新’数组的最高位索引),设置标志位mark(用于记录元素出现的次数),当mark的值大于一的时候替换(index+1)位置的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int index = 0;
int mark = 0;
if (nums.size()==0){
return 0;
}
for (int i=1;i<nums.size();i++){ //从第二个元素开始遍历
if (nums[index] != nums[i]){ //与index位置元素值不同,则替换index+1的位置元素的值
nums[++index] = nums[i];
mark = 0; //mark清空
}
else{
mark++;
if (mark < 2){ //相同的元素个数小于两个,无需剔除
index++;
nums[index]=nums[i]; //将该元素写入‘新’数组中
}
}
}
return index+1;
}
};

大神解法 [16ms]

每次比较连续三个元素,如果第三个和第一个元素不同,则这三个元素都无需剔除,在遍历数组时可以从第三个元素开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int i = 0 ;
for (int n:nums){
if (i<2 or n> nums[i-2]){
nums[i]=n;
i++;
}
}
return i;

}
};

本文标题:LeetCode 解题记录

文章作者:定。

发布时间:2017年2月15日 - 21时02分

本文字数:2,208字

原始链接:http://cocofe.cn/2017/02/15/LeetCode学习记录/

许可协议: Attribution-NonCommercial 4.0

转载请保留以上信息。