>

LoeiJe

:D 获取中...

何以解忧？唯有暴富

删除数组中重复元素

删除数组中重复元素

方法：双指针法。

算法：数组排完序后，放置两个指针i和j，其中i是慢指针，j是快指针，只要nums[i] = nums[j],就增加j跳过重复项，当遇到nums[j]≠nums[i]时，跳过重复项运行已经结束，因此把nums[j]的值复制到nums[i+1]然后递增i；接着重复相同的过程，直到j到达数组末尾！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 删除数组中的重复项.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
	int removeDuplicates(vector<int>& nums) {
		if (nums.empty()) return 0;
		int len = nums.size();
		int i = 0;
		for (int j = 1; j < len; j++)
		{
			if (nums[i] != nums[j])
			{
				nums[++i] = nums[j];
			}
		}
		return i + 1;
	}
};

int main()
{
	vector<int> a;
	a.push_back(1);
	a.push_back(1);
	a.push_back(2);
	a.push_back(3);
	Solution s;
	int len;
	len = s.removeDuplicates(a);
	for (int i = 0; i < len; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}

移除元素方法类似，不过需要从j=0开始，并且需要判断第一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 移除元素.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
	int removeElement(vector<int>& nums, int val) {
		if (nums.empty()) return 0;
		int len = nums.size();
		int i = 0;
		for (int j = 0; j < len; j++)
		{
			if (nums[j] != val) {
				nums[i++] = nums[j];
			}
		}
		return i;
	}
};

int main()
{
	vector<int> a;
	a.push_back(2);
	a.push_back(1);
	a.push_back(2);
	a.push_back(12);
	a.push_back(2);
	Solution ws;
	int len = ws.removeElement(a, 2);
	for (int i = 0; i < len; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}
Leedcode, 算法