分治

例题

LeetCode23

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例1

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

提示

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

解题思想

可以将一组链表分成两两一组，如果为单数则自成一组
将每组合并成新的一组链表，此时链表数组长度为原来的一半
以此类推，每次只需要合并 k/(2^i) 次，则总时间复杂度为O(logk)

示例代码

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        // 获取数组长度
        if (len == 0) return null;
        // 如果数组为空，直接返回空
        while (len > 1) {
            // 当待合并长度大于1，则仍能合并
            for (int i=0; i<len-1; i+=2) {
                // 两两合并
                lists[i / 2] = mergeTwoLists(lists[i], lists[i + 1]);
            }
            if (len % 2 == 1) {
                // 如果长度为奇数，则剩余一个不需要合并直接放到下一合并数组中
                lists[(len + 1) / 2] = lists[len-1];
            }
            len = (len+1)/2;
            // 下一合并数组的长度
        }
        return lists[0];
        // 返回合并数组的第一个（结果）
    }

    // 合并两个链表
    public static ListNode mergeTwoLists(ListNode x, ListNode y) {
        ListNode p = new ListNode(0);
        ListNode head = p;
        // p 为移动节点 head 为头节点
        while (x != null && y != null) {
            // 当 x、y 均不为空
            if (x.val < y.val) {
                // 取最小值
                p.next = x;
                p = x;
                x = x.next;
                // p.next 指向 x，且 p、x 均向下移动
            } else {
                // 同理
                p.next = y;
                p = y;
                y = y.next;
            }
        }
        if (x == null) {
            // 如果 x 为空，则将 y 剩余部分填入
            while (y != null) {
                p.next = y;
                p = y;
                y = y.next;
            }
        }
        while (x != null) {
            // 将 x 剩余部分填入
            p.next = x;
            p = x;
            x = x.next;
        }
        return head.next;
        // 返回头节点的下一节点
    }
}

---

LeetCode169

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例1

输入：nums = [3,2,3]

输出：3

示例2

输入：nums = [2,2,1,1,1,2,2]

输出：2

提示

n == nums.length

1 <= n <= 5 * 104

-109 <= nums[i] <= 109

解题思想

示例代码

public int majorityElement(int[] nums) {
    int result = nums[0];
    // 记录结果
    int count = 1;
    // 当前记录的结果重复的次数
    for (int i=1; i<nums.length; i++) {
        if (count == 0) {
            // 如果计数为0，则当前的数计入结果中，且计数置1
            result = nums[i];
            count = 1;
            continue;
        }
        // 如果是同样的数，则+1，否则-1
        if (nums[i] != result) count--;
        else count++;
    }
    return result;
}