LeetCode刷题笔记——HOT100面试题（5）

算法
, ,

快速排序

215. 数组中的第K个最大元素

使用快速排序的partition函数求第K个最大的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Random;

class Solution {
    Random random = new Random(1);
    public int findKthLargest(int[] nums, int k) {
        return findKthLargest(nums, nums.length-k, 0, nums.length-1);
    }

    public int findKthLargest(int[] nums, int k, int lo, int hi) {
        int mid = lo + (hi-lo)/2;
        int p = partition(nums, lo, hi);
        if (p<k) return findKthLargest(nums, k, p+1, hi);
        else if (p>k) return findKthLargest(nums, k, lo, p-1);
        else return nums[p];
    }

    public int partition(int[] nums, int lo, int hi) {
        //本题测试用例有极端情况（数组已经基本有序），此时快排时间复杂度达到O(n^2)，因此需要随机选择pivot
        if (lo<hi) {
            int randomIndex = lo+random.nextInt(hi-lo);
            swap(nums, lo, randomIndex);
        }
        int p = nums[lo];
        int i = lo, j = hi+1;
        while (true) {
            while (j>lo && nums[--j]>p);
            while (i<hi && nums[++i]<p);
            if (i>=j) break;
            swap(nums, i, j);
        }
        swap(nums, j, lo);
        return j;
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

二维数组的排序

56. 合并区间

对每个区间按照首位元素排序。如果区间1的右边界大于区间2的左边界，则可以合并，右边界取两者右边界的较大者；否则区间2成为新的区间加入结果集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        LinkedList<int[]> res = new LinkedList<>();
        res.offer(intervals[0]);
        for (int i=1; i<intervals.length; i++) {
            int[] curr = res.peekLast();
            if (curr[1]<intervals[i][0]) {
                res.offer(intervals[i]);
            } else {
                curr[1] = Math.max(intervals[i][1], curr[1]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

253. 会议室 II

只需要考虑同时占用的会议室的最大值，无需考虑是哪个会议开始或结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] start = new int[n];
        int[] end = new int[n];
        for (int i=0; i<n; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int i = 0, j = 0, cur = 0, res = 0;
        while (i<n) {
            if (start[i] < end[j]) {
                cur++;
                res = Math.max(res, cur);
                i++;
            } else if (start[i] > end[j]) {
                cur--;
                j++;
            } else {
                i++;
                j++;
            }
        }
        return res;
    }
}

406. 根据身高重建队列

先按照身高从高到低的顺序排列，相同的身高的按照第二项的值从小到大排序；首先安排身高高的，再将剩下的身高低的逐个插入有序的队列中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]==o2[0]? o1[1]-o2[1]: o2[0]-o1[0];
            }
        });
        ArrayList<int[]> tmp = new ArrayList<>();
        for (int[] p: people) {
            tmp.add(p[1], p);
        }
        int[][] res = new int[people.length][2];
        for (int i=0; i<people.length; i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }
}

二分查找

33. 搜索旋转排序数组

二分查找，根据nums[mid]与两边的大小关系，确定旋转发生在中点的哪一侧，缩小目标数所在的区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && nums[mid] >= target) right = mid;
                else left = mid + 1;
            } else {
                if (nums[mid] <= target && nums[right] >= target) left = mid;
                else right = mid - 1;
            }
        }
        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

查找目标元素在数组中出现的左边界和右边界。参见《剑指offer》数字在排序数组中出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {

    int[] nums;
    int target;

    public int[] searchRange(int[] nums, int target) {
        this.nums = nums;
        this.target = target;
        int l = getLeft();
        int r = getRight();
        return new int[]{l, r};
    }

    public int getLeft() {
        int l = 0, r = nums.length-1;
        while (l<=r) {
            if (l==r) return nums[l]==target? l: -1;
            int m = l + (r-l)/2;
            if (nums[m]==target) r = m;
            else if (nums[m]>target) r = m-1;
            else l = m+1;
        }
        return -1;
    }

    public int getRight() {
        int l = 0, r = nums.length-1;
        while (l<=r) {
            if (l==r) return nums[l]==target? l: -1;
            int m = l + (r-l)/2 + 1;
            if (nums[m]==target) l = m;
            else if (nums[m]>target) r = m-1;
            else l = m+1;
        }
        return -1;
    }
}