配列の重複を見つける。
正答率58%
((552.0/(552 +398))*100).round
設問
Imagine we have an immutable array of size N which we know to be filled with integers ranging from 0 to N-2, inclusive. Suppose we know that the array contains exactly one duplicated entry and that duplicate appears exactly twice. Find the duplicated entry. (For bonus points, ensure your solution has constant space and time proportional to N)
Input sample:
Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Ignore all empty lines. Each line begins with a positive integer(N) i.e. the size of the array, then a semicolon followed by a comma separated list of positive numbers ranging from 0 to N-2, inclusive. i.e eg.
5;0,1,2,3,0 20;0,1,10,3,2,4,5,7,6,8,11,9,15,12,13,4,16,18,17,14
Output sample:
Print out the duplicated entry, each one on a new line eg
0 4
やってみた
#!/usr/bin/env ruby #http://d.hatena.ne.jp/takuya_1st/20100103/1262486833 def verify_duplication(ar) ar.uniq.find{ |e| ar.index(e) != ar.rindex(e) } end ARGF.lines do |line| next if line.strip == '' puts verify_duplication(line.chomp.split(';')[1].split(',')) end
重複しているものだけ取り出す、Array#uniqの逆が思いつかなくて
ググったら下記URLで面白いやり方をしていたので
参考にして書いてみた。
indexとrindexを比較するという、目から鱗な書き方。
