Lexi's Leetcode solutions

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

这个算法挺难想到的。让O(n)说明不能sort，那只能用container。但是用container怎么traverse连续的呢？又不能sort key。所以，我们人眼是怎么做这个题的呢，上来是100，我们其实就想找99和101，有的话就接着那个方向，直到找不着了为止。这样算过的数就从set里删掉，既然是别人的连续，那也是自己的连续，所以不用看了。这样过一遍就能把所有连续数列找全，没有元素重复处理的。

public int longestConsecutive(int[] num) {
    int res = 0;
    Set<Integer> set = new HashSet<Integer>();
    for (int i : num)
        set.add(i);
    for (int i = 0; i < num.length && !set.isEmpty(); i++) {
        int len = 0;
        //go up
        for (int j = num[i] - 1; set.contains(j); j--) {
            set.remove(j);
            len++;
        }
        //go down
        for (int j = num[i]; set.contains(j); j++) {
            set.remove(j);
            len++;
        }
        res = Math.max(res, len);
    }
    return res;
}

给一个无序int array，有正有负，找第一个missing正整数。比如[3,4,-1,1] return 2.要求O(n)时间，O(1)空间。

思路：

• 要求这么高，还不让用空间换时间，说明不是dp，所以基本只让过一两遍数组，一边过一遍直接in place的改动数组（不让生成新数组啊）
• 既然是大部分不missing，所以可以用index来直接和元素产生关系。
• 试图让A[i]这个值x的index是x – 1，即每个index身上的元素都是index本身+1。所以{1 2 3}就是理想中的新数组，{1 5 3}就说明缺2。

算法：

1. 如果A[i]不在自己该在的地方，就想办法把他换到该在的地方。如果A[i]是<=0或者A[i]比数组长度还大，说明没有它该在的地方，那就skip他，弄下一个（不用担心当前位置被它占了，如果后面有想在这个位置的正整数，它会被换走的）
2. A[i]和A[A[i] – 1]换，然后继续回到i，接着换，直到第一种情况满足。但是如果这俩数一样，换也没用，就别原地打转了。
3. 最后过一遍shift过的array，第一个不在原位的就是。

public int firstMissingPositive(int[] A) {
  for (int i = 0; i < A.length; i++) {
    //if it's not in its supposed to be place (the index of value x should be x - 1)
    if (i != A[i] - 1){
      if (A[i] <= 0 || A[i] > A.length || A[i] == A[A[i] - 1])
        continue;
      else {
        //put A[i] to A[A[i] - 1]
        swap(A, i, A[i] - 1);
        i--; //回到刚才这位接着做
      }
    }
  }
  for (int i = 0; i < A.length; i++) {
    if (i != A[i] - 1)
      return i + 1;
  }
  return A.length + 1;
}

看了http://www.cnblogs.com/AnnieKim/archive/2013/04/21/3034631.html的答案才会的。