Uniqueness

생활의 달인을 보면, 매회마다 최고의 달인들이 출연한다. 그들의 클로징멘트는 모두가 대부분 유사한데, "돈을 많이 벌어서 앞으로 내 가게를 차리는게 꿈이다"는 것. 그 분야에서 최고가 되었는데 큰 돈은 벌지 못하였나보다. 왜 일까? 그거슨 바로 a lack of uniqueness.

자료구조와 알고리즘을 빠삭하게 꾀고 있는 베스트 프로그래머가 될 필요는 없다. 그래봐야 그냥 우수한 코더가 될 뿐이니까.

우선순위

해야할 일들이 쌓여있는데 미래가치를 봐야할지 당장의 닥친 일이 우선인지 저울질하기 힘든 요새다. 아바타 조작하듯 제 3자 입장에서 생각하면 좀 더 과감해질지도!

Finding Kth largest element in Array

See Selection Algorithm first: http://en.wikipedia.org/wiki/Selection_algorithm

package org.udanax.eddieyoon.codeguru;

public class KthLargest {

  public static void main(String[] args) {
    int[] x = new int[] { 3, 6, 92, 34, 1, 35, 62, 13, 12, 24, 53 };
    System.out.println(getKthLargest(x, 3));
  }

  private static int getKthLargest(int[] x, int k) {
    int low = 0;
    int high = x.length - 1;

    while (true) {
      int pivot = (low + high) / 2;
      int newPiv = partition(x, low, high, pivot);

      if (newPiv == k) {
        return x[newPiv];
      } else if (newPiv < k) {
        low = newPiv + 1;
      } else {
        high = newPiv - 1;
      }
    }
  }

  private static int partition(int[] x, int left, int right, int pivot) {
    int pivValue = x[pivot];
    swap(x, pivot, right);
    int storePos = left;

    for (int i = left; i < right; i++) {
      if (x[i] < pivValue) {
        swap(x, i, storePos);
        storePos++;
      }
    }
    swap(x, storePos, right);
    return storePos;
  }

  private static void swap(int[] x, int a, int b) {
    int temp = x[a];
    x[a] = x[b];
    x[b] = temp;
  }

}