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

  1. abraxsus wrote:

    머야.. 소팅하고나서 찾잖아-_-;
    정녕 이것뿐이란 말인가.
    이게 optimal인건가..
    소팅되지 않는 종류의 데이터들에 대해서는 어떻게 되는거지?
    equality만 존재하고 크기관계가 없는 데이터에 대해서는?

    Posted 20 Jul 2006 at 2:36 am
  2. MKSeo wrote:

    흠. 그런 예는 잘 모르겠지만 아마도
    one way hashing with very little possibility of collision? MD5 같은?
    worst case 로 했을때 O(nlogn)이 lower bound거든.
    근데 사실 말이 쉽지, nlogn이 하한인거 모르고 덜컥 소팅하고
    찾으면 되잖아요라고 말하기는 어려움.

    Posted 20 Jul 2006 at 2:48 am
  3. MKSeo wrote:

    실은 파이썬 연습목적도 있음 ㅎㅎ

    Posted 20 Jul 2006 at 2:48 am
  4. abraxsus wrote:

    ㅋㅋ.. 머야.. 여기가 연습장이냐! ㅎㅎㅎ
    물론, 동감. nlogn이 하한이라는거 모르고 이러면 되잖아요.. 라고 말할수는 없지..
    중요한건 그게 하한이라는거니까…. 근데 어떻게 증명되냐-_-;;

    그리고, 내 생각엔 대소관계가 없는(쉽게 생각해서 복소수같은거) 데이터들에
    대해서는 하한이 n^2일것같다. 대소관계가 정의될경우에나 nlogn이 가능할듯한데.
    음..

    Posted 20 Jul 2006 at 3:41 am
  5. MKSeo wrote:

    복소수는…. a+bi, c+di 면 a먼저 비교하고 b, d 비교하고 이러면 되잖아.
    순서만 정하면 되니까.. 순서는 얼마든지 정할 수 있을거 같은데 ㅎㅎ

    그리고 심심한가본데 내가 문제하나 낼까? ㅋㅋ
    Q) 숫자 나열이 주어졌을때, 합이 0에 가장 가까운 서브 벡터를 찾으시오.

    예를들자면, 1,3,2,1,-1,7 이면 [1,-1] 이 합이 0에 가장 가깝지.
    또 예를들어, 80,70,5,-4,-1,8,100 이면 [5,-4, -1] 이 답이지.

    잘 아는 maximum subvector sum 의 변형판이야.. 물론 nlogn에 풀어야함.
    내가 낼 파이썬 코드로 올리지 ㅎㅎ

    아;; 그리고 증명은 숫자 n개가 있을때 얘네를 위의 코드가 출력하는 답처럼
    파티션을 나눠놓는다고 하자. 그럼 첫번째 수 a1가 있다고 할때, 두번째 수 a2는
    a1과 같거나 다르다. 세번째수 a3은 a1과 같거나 a2와 같거나 아니면 그 둘 모두와
    다르다. a4는 a1과 같거나 a2와 같거나 a3과 같거나 그 모두와 다르다. 뭐
    이런식으로하면 1*2*3*…*n 이 되서 n! 의 방법으로 파티셔닝을 할 수 있다는
    사실을 알 수 있다. 따라서 decision tree를 통해 파티션을 나눠놓는다고하면
    height가 nlogn. 여기까지가 내 생각인데 진규넘은 맞다고 하더군.

    Posted 20 Jul 2006 at 6:53 am
  6. 공성식 wrote:

    이거 버그 아닌가요?

    [[1, 1], [3, 3], [4]]
    [[1, 1], [2, 2], [3, 3, 3], [5, 5]]

    이런 식으로 결과가 나와야 할 것 같은데…

    for i in xrange(1, len(sorted_list)):
    이것 때문인 것 같네요.
    for i in xrange(0, len(sorted_list)):
    이렇게 고치면 될 것 같구요.

    아니면 제가 문제를 잘못 이해한 걸까요?

    Posted 20 Jul 2006 at 1:10 pm
  7. 공성식 wrote:

    저도 한때는 파이썬에 흠뻑 빠진 적이 있습니다만 루비를 알고나서부턴 많이 멀어졌어요.
    There’s only one way to do it…이라는 미니멀리즘 철학은 참 좋았던 것 같은데…

    루비로 만들어봤어요.
    속도는 글쎄요… (미리 소트하지 않고 결과만 소트하므로 괜찮을 것 같습니다만.)
    저는 속도보다는 golfing을 즐기는 편이라…:-)

    def u a
    a.inject(Hash.new(0)) {|m, i| m[i] += 1; m}.sort_by{|k, v| k}.inject([]) {|m, i| m.push [i[0]] * i[1]}
    end

    p u([1,3,4,3,1])
    p u([1,3,5,3,2,1,5,3,2])

    push 대신 연산자를 쓰면 더 짧아지겠지만 여기서 깨질까봐서…

    Posted 20 Jul 2006 at 1:14 pm
  8. 공성식 wrote:

    두 분 대화에 끼어들어 죄송합니다.
    재밌는 문제를 보면 사죽을 못 쓰는 성격이라…
    아주 단순 무식하게 작성한 것입니다.(brute force…hehe)

    def comb arr
    return [arr] if arr.size == 1
    sub = comb(arr – [arr[0]])
    [[arr[0]]] + sub + sub.map {|i| [arr[0]] + i }
    end

    def nearest_zero arr
    comb(arr).sort_by {|i| i.inject(0) {|m, j| m + j}.abs}[0]
    end

    a = [1,3,2,1,-1,7]

    p nearest_zero(a)

    Posted 20 Jul 2006 at 2:32 pm
  9. JM wrote:

    partial sum sort!

    그나저나 element duplicate 의 존재만을 determine 하는데 O(nlgn) 이라는건 왠지 억울하네요. 더 낮은 시간 복잡도가 있어야 할 것 같은 기분이에요 ㅜㅜ

    Posted 20 Jul 2006 at 8:54 pm
  10. MKSeo wrote:

    역시 JM!! ㅋㅋㅋ
    네 partial sum sort.
    그냥 원래부터 알던건가요? -_-;;;;
    어디서 그런건 다 보고 아는건지 궁금해요..

    음 그리고 0번값을 array에 안넣은 버그네요;;;;
    루비는 이제 접을까 합니다…
    가장 큰 이유는 커뮤니티가 너무 약하다는 것..

    Posted 20 Jul 2006 at 9:29 pm
  11. abraxsus wrote:

    음.. 그래, 결국 duplicate의 결정은 partitioning문제로군.
    그리고, 0가까이 합구하는.. 이 문제는, 심심풀이 땅콩 문제가 아니자나!! -_-+++
    내가 심심하다는것이 참이라는것이 그렇다고 나를 괴롭혀도 된다는것을 의미하지는 않는다.
    -_-;;; 답안을 아직 살펴보지도 못했다.. 루비땜시..컹… 매력적인 언어야.흘
    뭐 국내 커뮤니티가 적은거지 밖에보면 커뮤니티 크자나..

    Posted 22 Jul 2006 at 10:18 am
  12. JM wrote:

    전에 partial sum 을 유용하게 여러 번 썼어서리.. :)
    근데 Programming Pearls 에 있는 문젠가요? 그럼 전에 풀어봤었겠네요. -_-;; 쿨럭;;

    Posted 23 Jul 2006 at 10:56 pm
  13. abraxsus wrote:

    공성식님과는 다르지만, 이렇게도…

    irb(main):100:0> [1,3,5,2,3,1].sort.inject([]) {|m,n| if (m[-1] && m[-1][0]==n)
    then m[-1] [[1, 1], [2], [3, 3], [5]]

    그냥 true/false만을 원하면,

    irb(main):125:0> def u a
    irb(main):126:1> a.sort.inject{|m,n| return true if m==n;n}
    irb(main):127:1> false
    irb(main):128:1> end

    Posted 20 Aug 2006 at 3:47 pm
  14. abraxsus wrote:

    에잉.. 코드 깨지넹..

    irb(main):100:0> [1,3,5,2,3,1].sort.inject([]) {|m,n| if (m[-1] && m[-1][0]==n)
    then m[-1].push( n) else m.push([n]) end;m }
    => [[1, 1], [2], [3, 3], [5]]

    Posted 20 Aug 2006 at 3:49 pm
  15. MKSeo wrote:

    @abraxsus: 루비 공부 많이 했군여;;;;;

    Posted 20 Aug 2006 at 11:16 pm
  16. abraxsus wrote:

    @mkseo: 짬짬이 들여다보고있읍니다-_-;;; 시간이 잘 안나서…;; 그 골핑인지 뭔지에 재미들여가고있는듯하군요.. 헐헐.. 루비, 맘에 들었음.

    Posted 21 Aug 2006 at 12:34 am
  17. MKSeo wrote:

    적응하느라 바쁜가보구나 ㅎㅎ

    Posted 21 Aug 2006 at 7:02 am

Post a Comment

Your email is never published nor shared.