分治算法例题_分治算法简单题

例题

以下例题均来自LeetCode
后续不再另注来源

众数

多数元素

• 如果一个数在数组nums里是众数即count(x) >= length/2 + 1
  • 那么该数的个数必比其他所有数的个数的总数还多
  • 将数组分为两份，该众数一定为其中一份的众数
• 尝试用分治法解决该问题，将原数组不断分解为比他小的子数组，寻找子数组中的众数，根据子数组中的众数判断原数组的众数
  • 基本情况：len == 1 ，数组里仅有一个元素的时候
  • 分解： mid = l(ow + high)/ 2
    • 原址操作，仅传递在数组中的索引
  • 解决：当问题规模为1的时候直接返回元素，问题规模大于1继续分解
  • 合并：这道问题的关键在于根据子数组中的众数判断原数组的众数
• nums有两个数组nums_1和nums_2。如果x是nums_1的众数，y是nums_2的众数
  • x == y ： x 是nums的众数
  • x ! = y ： 需要在整个区间内寻找x和y的数目比较哪个数更多 O(n)
• 最坏情况下：O(nlgn)

C++代码如下

int majorityElement(vector<int>& nums) {
   
        int len = nums.size();
        if(len == 1) return nums[0];
        else 
        {
   
            int n = len - 1;
            return SubElement(nums, 0, n);
        }
    }
    int SubElement(vector<int>& nums, int low, int high)
    {
   
        vector<int> rst;
        if (low == high)
            return nums[low];
        else
        {
   
            int mid = (low+high)/2;
            int left_element = SubElement(nums, low, mid);
            int right_element = SubElement(nums, mid+1, high);
            if(left_element == right_element)
            {
   
                return left_element;
            }
            else
            {
   
                int len = high-low+1;
                int left_count = 0;int right_count = 0;
                for(int i=low; i<len; ++i)
                {
   
                    if(nums[i] == left_element) ++left_count;
                    else if (nums[i] == right_element) ++ right_count;
                    else continue;
                }
                return left_count > right_count ? left_element : right_element;
            }
        }

    }
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
41
42
43
44
45

此题用分治算法并不是最优算法

相似例题

数组的度

• 在这道题里面我们还要得到与数组的度d相同的子数组的最短长度
• 如果我们继续尝试用分治法解决的话在源代码上我们需要增添一个max_nums数组存储d的最大元素（可能有多个最大元素个数为d的数组元素）
• 然后分别比较所有这些元素的最小长度

需要添加的伪代码如下

len_max_nums = len(max_nums);
rst = len + 1;
for i = 0 to len_max_nums - 1

2	target = max_nums[i]
	for j = 0 to len
		if (nums[j] == target)
			left_cur = j
			break
	for j = len down to 0
		if(nums[j] == target)
			right_cur = j
			break
	rst = min(rst, right_cur - left_cur + 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 除了继续用分治以外我们思考以下两种解题思路
• hash
  • hash函数可以使我们以O(1)的时间访问到所hash的值指向的数据
  • 如果一个元素x其个数为d（数组的度为d）那么其最后一个出现x元素的坐标right_cur和最先出现的坐标left_cur。sub = right_cur - left_cur + 1。对所有元素个数为d产生的sub选取最小值

扩展

合并两个排序的链表

合并两个排序的链表

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
   
        if (l1 == NULL)
            return l2;
        else if(l2 == NULL)
            return l1;
        else
        {
   
            ListNode* rst = new ListNode(-1);
            ListNode* pre = rst;
            while(true)
            {
   
                if(l1->val >= l2->val)
                {
   
                    pre->next = new ListNode(l2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17