去重

缘起

数组去重是常见的面试题， 而且也是基本的操作.

分析

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "stdafx.h"
#include <iostream>
#include <algorithm>

#pragma warning(disable:4996)

//#define LOCAL
using namespace std;

const int MAX_N = 105;

int unique(int *a, int n) // 不进行排序情况下去重, 函数返回去重之后剩余元素的个数
{
	bool flag[MAX_N];
	memset(flag, 0, sizeof(flag));
	for (int i = 0; i<n-1;i++)
	{
		if (flag[i]) continue;
		for (int j = i+1; j<n; j++) if (a[i] == a[j]) flag[j] = true;
	}
	int j = 0;
	for (int i = 0; i<n;i++)
	{
		if (flag[i]) continue;
		a[j++] = a[i];
	}
	return j;
}

int unique_with_sort(int *a, int n) // 排序之后再去重, 返回最后去重之后元素的个数
{
	sort(a, a+n); // 升序排序
	int i, j;
	for (i = 0,j=1; j<n;)
	{
		while(a[i] == a[j]) j++;
		if (j<n) a[++i] = a[j];
	}
	return i+1; // a[0,...i]
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif
	
	int a[] = {4, 2,2,4,6,7,6,3};

	// 不排序情况下的去重, 复杂度为O(n^2)
	/*
	int res = unique(a,8);
	printf("去重之后剩余如下%d个元素:\n", res);

	for (int i = 0;i<res;i++)
	{
		printf("%d ",a[i]);
	}
	puts("");
	*/


	// 先排序, 再去重, 复杂度是O（nlogn）
	int res = unique_with_sort(a,8);
	printf("去重之后剩余如下%d个元素:\n", res);
	for (int i = 0;i<res;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}