88. Merge Sorted Array

既然题目都说了nums1的长度足够长，那就不管了直接从最后面放元素。

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1 == null || nums2 == null) return;

        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else nums1[k--] = nums2[j--];
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

287. Find the Duplicate Number

这题有点意思，原理不是太好想。借鉴 Linked List Cycle 的思想，如果存在至少一个重复值的话，那个重复值必为cycle的入口。对于数组来说，如果一个数组没有重复值，那么每一对数值和下标都能形成独立的映射，就像数组的表示形式一样，index -> num[index]一一对应。相应的，这里再加层映射，形式为 num[i] -> num[num[i]]。如果映射唯一，即数组没有重复值。

用快慢指针来找入口，慢指针每次映射一次，快指针每次映射两次。

public int findDuplicate(int[] nums) {
        int slow=0, fast=0;
        do{
            slow=nums[slow];
            fast=nums[nums[fast]];
        }while(slow!=fast);
        int st=0;
        while(st!=slow){
        st=nums[st];
        slow=nums[slow];
        }
        return slow;
}