剑指 Offer 03. 数组中重复的数字

方法1:朴素法

class Solution {
    public int findRepeatNumber(int[] nums) {
        boolean[] arr = new boolean[nums.length];
        for (int n : nums) {
            if (arr[n]) return n;
            arr[n] = true;
        }
        return nums[0];
    }
}

方法2:归位法

class Solution {
    public int findRepeatNumber(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                int tmp = nums[i];
                if (nums[tmp] == tmp) return tmp;
                nums[tmp] = tmp;
                nums[i] = tmp;
            }
        }
        return -1;
    }
}

剑指 Offer 40. 最小的k个数

方法1：partition法，思想和快排类似。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr == null || arr.length == 0) return arr;
        int end = arr.length - 1;
        int start = 0;
        while (start <= end) {
            int pivot = partition(arr, start, end);
            if (pivot < k - 1) {
                start = pivot + 1;
            } else if (pivot > k - 1) {
                end = pivot - 1;
            } else {
                break;
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = arr[i];
        }
        return res;
    }
    private int partition(int[] arr, int start, int end) {
        int v = arr[start];
        int j = start; //[start+1, j] < v
        for (int i = start + 1; i <= end; i++) {
            if (arr[i] < v) {
                swap(arr, i, ++j);
            }
        }
        swap(arr, start, j);
        return j;
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

方法2：使用大顶堆

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k < 1) return new int[0];
        if (k >= arr.length) return arr;
        PriorityQueue<Integer> queue = new PriorityQueue<Integer> ((k1, k2) -> k2.compareTo(k1));
        for (int e : arr) {
            if (queue.size() < k) {
                queue.add(e);
            } else if (queue.peek() > e){
                queue.poll();
                queue.add(e);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
}