元素唯一性

1 元素唯一性-暴力法

问题描述

检验数组中元素的惟一性

算法原理

暴力法

1
2
3
4
5
6
7
UniqueElements(A[1,…n])
//输出：如果A之元素全部惟一，返回“true”, 否则返回 “false”

for i←1 to n-1 do
	for j← i+1 to n do
		if A[i]=A[j] return false
return true

算法效率

n(n-1)/2

2 元素唯一性-预排序

算法原理

1
2
3
4
5
6
7
8
9
PresortElementUniqueness(A[1..n])
//先对数组排序来解元素惟一性问题
//输入：n个可排序元素构成的一个数组A[1..n]
//输出：如果A没有相等的元素，返回“true”, 否则返回”false”

对数组A排序
for i← 1 to n-1 do
 	if A[i] = A[i+1] return false
return true

算法效率

T(n)=Tsort(n) + Tscan(n) ∈Θ (nlogn) +Θ (n) = Θ (nlogn)