如何找出数组中重复的元素


#算法#


2014-09-08

这个问题可以变形成多个问题:
1、找出数组中多次出现过的元素。
2、找数组中只出现1次的元素。
3、找到数组中没有出现的元素。例如,整型数组中最小元素是a,最大是b,在a和b之间哪些整数没有在数组中出现过?

hash方法

用hash来统计元素的出现次数,这样就可以轻易得解决问题1和问题2。

# !/usr/bin/env ruby
# coding: UTF-8

arr = [1, 2, 9, 8, 3, 9, 20, 2, 9, 8]

hs = Hash.new
arr.each { |e|
	if hs.has_key?(e)
		hs[e] += 1
	else
		hs[e] = 1
	end
}

p hs

结果是:

{1=>1, 2=>2, 9=>3, 8=>2, 3=>1, 20=>1}

然后遍历Hash对象hs即可。

Hash类在动态语言中都得到了很好的实现,其本身的实现有多种方法。如果要用C语言来实现,代码量会偏大。

位向量

这种方法适合数组元素是整数的情况。基本想法是:如果待处理数组的最小元素是0,定义一个较大的bit类型的新的数组,第1个bit(索引是0)代表数字0,第二个bit代表数字1,依次类推。这些bit的值默认是0。如果待处理数组中某元素为c,则将bit数组的第c+1个元素置1,根据这种方式来处理待处理数组中的所有元素。最终,扫描bit数组,就可以知道那些数字出现过,哪些数字没出现过。这种方法可以解决问题3。

为拓展这种方法可解决问题的范围,可以将新数组定义为整数类型,这样就可以记录某个数字出现的次数。其实也是一种Hash。

代码如下:

# !/usr/bin/env ruby
# coding: UTF-8

arr = [1, 2, 9, 8, 3, 9, 20, 2, 9, 8] # 待处理数组,所有元素必须大于等于0,且为整数

new_arr = Array.new(arr.max+1, 0)

for e in arr
	new_arr[e] += 1
end

for e in arr
	print e, "\t", new_arr[e], "\n"
end

运行结果如下(注意输出结果有重复):

1	1
2	2
9	3
8	2
3	1
9	3
20	1
2	2
9	3
8	2

这种方法可以解决问题1、2、3,也对数组arr进行了排序,问题是空间使用量可能较大(例如数组arr中加入新元素20000,那么new_arr的size将是20001)。

链表+插入排序

上面位向量的方法在遇到极端的情况时,可能会比较浪费内存,要避免这种情况可以使用链表。结合插入排序,实现如下:

# !/usr/bin/env ruby
# coding: UTF-8

arr = [1, 2, 9, 8, 3, 9, 20, 2, 9, 8] # 待处理数组,所有元素必须大于等于0,且为整数

class LinkedList
	
	class Node
		attr_accessor :data, :times,:next
		def initialize(data, next_node=nil)
			@data = data
			@times = 1
			@next = next_node
		end
	end
	
	def initialize
		@root = nil
	end

	def insert(num)
		if @root.nil?
			@root = Node.new(num)
			# puts "debug: @root is nil"
			return
		end
		current_node = @root
		while true

			if current_node.data == num
				current_node.times += 1
				break
			end

			if current_node.next.nil?
				new_node = Node.new(num)
				current_node.next = new_node
				break
			end

			if current_node.data < num && current_node.next.data > num
				new_node = Node.new(num)
				new_node.next = current_node.next
				current_node.next = new_node
				break
			end

			current_node = current_node.next
					
		end
	end

	def show
		current_node = @root
		while not current_node.nil?
			print current_node.data, "\t", current_node.times, "\n"
			current_node = current_node.next
		end
	end
end

linked_list = LinkedList.new
for e in arr
	linked_list.insert(e)
end
linked_list.show

运行结果如下:

1	1
2	2
3	1
8	2
9	3
20	1

排序法

这个方法算是比较巧妙的。先看一下一个数组的排序结果:

# !/usr/bin/env ruby
# coding: UTF-8

arr = [1, 2, 9, 8, 3, 9, 20, 2, 9, 8] 
p arr.sort

运行结果如下:

[1, 2, 2, 3, 8, 8, 9, 9, 9, 20]

对这个运行结果,如果要解决问题1(找出多次出现过的元素),可以这样做:

# !/usr/bin/env ruby
# coding: UTF-8

arr = [1, 2, 9, 8, 3, 9, 20, 2, 9, 8] 
arr = arr.sort
# now arr is [1, 2, 2, 3, 8, 8, 9, 9, 9, 20]

position = 0

while position < arr.size-1
	cur = arr[position]
	if arr[position] == arr[position+1]
		puts arr[position] # 这个数字多次出现
		while arr[position+1] == cur && position < arr.size-1 # 找下一个不同的数
			position += 1
		end
	else
		position += 1
	end
end

运行结果是:

2
8
9

要解决问题2(找数组中只出现1次的元素),找那些和左侧、右侧数字都不相等的数字即可。

要解决问题3(找到数组中没有出现的元素),找到相邻的两个不等的数字,输出这两个数字的中间的数字即可。


( 本文完 )