Element uniqueness

Determine the existence of duplicates. O(nlogn) is optimal.

#!/usr/bin/python

import copy

def elem_uniq(val_list):
        result = [[]]

        sorted_list = copy.deepcopy(val_list)
        sorted_list.sort()

        prev_val = sorted_list[0]
        result[-1].append(prev_val)
        for i in xrange(1, len(sorted_list)):
                cur_val = sorted_list[i]

                if prev_val == cur_val:
                        result[-1].append(cur_val)
                else:
                        prev_val = cur_val
                        result.append([cur_val])


        return result

print elem_uniq([1,3,4,3,1])
print elem_uniq([1,3,5,3,2,1,5,3,2])

Output:

mkseo@mkseo:~/tmp$ ./elem_uniq.py
[[1], [3, 3], [4]]
[[1], [2, 2], [3, 3, 3], [5, 5]]
mkseo@mkseo:~/tmp$

Updated: bug fix on 21 July. Thanks SamKong!

Similar Posts:

Comments 17