Algorithm + Data Structures = Programs

本文最后更新于 2024年10月19日 晚上

问题描述

设有 nn 个互不相同的元素 x1,x2,⋯ ,xnx_1,x_2,\cdots,x_n，每个元素 xix_i 带有一个权值 wiw_i，且 ∑i=1nwi=1\sum_{i=1}^nw_i=1。若元素 xkx_k 满足 ∑xi<xkwi≤12\sum_{x_i < x_k}w_i \leq \frac{1}{2} 且 ∑xi>xkwi≤12\sum_{x_i > x_k}w_i \leq \frac{1}{2}，则称元素 xkx_{k} 为 x1,x2,⋯ ,xnx_{1},x_{2},\cdots,x_{n} 的带权中位数。请编写一个算法，能够在最坏情况下用 O(n)O(n) 时间找出 nn 个元素的带权中位数。

提交示例：

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
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

// 算法要求：请编写一段代码，能够在最坏情况下用 O(n) 时间找出 n 个元素的带权中位数
// 函数原型： 
void WeightMedian(int length,vector<int>num, vector<double>weight,int index){
	
}
//你的代码只需要补全上方函数来实现算法
//其中length为输入长度，num是包含n个互不相同元素值的向量，
//weight是包含元素值对应的权重的向量，index为递归调用时的索引(下标)
//只需要提交这几行代码，其他的都是后台系统自动完成的。类似于 LeetCode

int main() {
	// 后台自动给出测试代码放在这里，无需同学编写
	//测试代码将测试用例的三行数据分别导入length，num，和weight中
	//调用WeightMedian(length,num, weight,index)函数，
	//函数内部使用cout输出得到的中位数，测试代码默认index初始值为0
	return 0;	
}

样例输入：

1
2
3
int length = 10;
int num = {13825, 28995, 18417, 92445, 86407, 90546, 46896, 14757, 89837, 18252}; 
double weight = {0.08720404, 0.09585595, 0.12070109, 0.02521966, 0.01221968, 0.12648725, 0.13076193, 0.19128049, 0.15673069, 0.05353921};

样例输出：

1
28995

问题分析

如果采用暴力算法，可以先对 num 数组进行排序，再顺次检查权重和，这种方法在最坏情况下的时间复杂度为 O(n2)O(n^2)。若想要实现 O(n)O(n) 的复杂度，必须要使用递归的方法来设计算法，并需要在每个迭代步尽可能缩小问题规模。

算法设计

算法步骤

步1： 定义结构体 Node，num 中的值为 node.value，weight 中的值为 node.weight，将 num,weight 输入数组 nodes 中，转步2；

步2： 判断是否是单元素，单元素直接返回本身；否则，转步3；

步3： 使用 O(n)O(n) 的算法查找出本步数组的中位数 m_Median，以 m_Median 为基准将原数组划分成两半：其下标 pivot 左侧元素均小于 m_Median，右侧元素均大于 m_Median，转步4；

步4： 判断 M_Median 以左（不包含）累计权重 L_Sum 是否合规。计算本轮中的 L_Sum，若满足题目要求，则返回本轮 m_Median 的值。否则，若 L_Sum ≥\geq 1/2，则向左递归；反之，则向右递归。转步2。

时间复杂度分析

由上述算法可知，每次递归原问题规模缩小1/2；在每次迭代中，每次做划分的时间开销为 O(n)O(n)，每次求中位数的时间开销为 O(n)O(n)，每次求 L_Sum 的时间开销也是 O(n)O(n)。因此，在规模为 nn 的问题下，迭代步的开销为 O(n)O(n)。于是可得如下递归式：

T(n)={O(1)n=1T(n/2)+O(n)n>1\begin{equation*} T(n) = \begin{cases} O(1)&\quad n = 1\\ T(n/2)+O(n)&\quad n>1 \end{cases} \end{equation*}

令 n=2tn = 2^t，则

T(n)=T(2t)=T(2t−1)+O(2t)=⋯=T(1)+∑k=1tO(2k)=O(1)+O(2t+1−1)=O(n)\begin{align*} T(n) &= T(2^t) = T(2^{t-1}) + O(2^t) = \cdots = T(1) + \sum_{k = 1}^{t} O(2^k) \\ &= O(1) + O(2^{t+1} - 1) = O(n) \end{align*}

综上，其在最坏情况下时间复杂度为 O(n)O(n)，符合题意。

算法实现

定义结构体

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义结构体 Node
struct Node {
    int value;    // 元素值
    double weight; // 元素的权重
};

构建分区函数

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
// 划分函数，以 nodes[right] 作为主元进行划分，并返回主元最终位置的下标
// 将原数组按照主元重新排布，主元左侧均小于主元，主元右侧均大于主元
int Partition1(vector<Node>& nodes, int left, int right) {
    int p = left - 1; // 初始化分区指针
    for (int index = left; index < right; index++) {
        if (nodes[index].value <= nodes[right].value) {
            p++;
            swap(nodes[p], nodes[index]);
        }
    }
    swap(nodes[p + 1], nodes[right]);
    return p + 1; 
}

// 划分函数，使用指定元素 pivot 作为主元进行划分
int Partition2(vector<Node>& nodes, int left, int right, Node pivot) {
    // 找到元素 pivot 并将其与 nodes[right] 交换
    for (int i = left; i < right; i++) {
        if (nodes[i].value == pivot.value) { // 匹配元素 pivot
            swap(nodes[i], nodes[right]); // 将 pivot 移到 right 位置
            break;
        }
    }
    return Partition1(nodes, left, right);
}

查找中位数

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
46
// Select 函数的声明，用于查找第 i 小的元素，并返回该元素
Node Select1(vector<Node>& nodes, int left, int right, int order);

// 插入排序函数，对小数组排序并返回其中第 k 小的元素
Node Insert(vector<Node>& nodes, int start, int end, int k) {
    for (int i = start + 1; i <= end; i++) {
        Node cur_node = nodes[i]; // 暂存当前元素
        int j = i;
        // 将当前元素插入到已排序部分的合适位置
        while (j > start && nodes[j - 1].value > cur_node.value) {
            nodes[j] = nodes[j - 1]; // 向右移动元素
            j--;
        }
        nodes[j] = cur_node;
    }
    return nodes[start + k - 1]; // 返回排序后的第 k 小元素
}

// 线性时间查找数组元素的中位数，返回该中位数
Node findMedian(vector<Node>& nodes, int left, int right) {
    int length = right - left + 1; // 计算数组长度
    vector<Node> medians((length + 4) / 5); // 用于存放每组中位数
    int m_index = 0;
    // 每 5 个元素一组，排序后取组内中位数
    for (int i = left; i <= right; i += 5) {
        int end = min(i + 4, right);
        medians[m_index++] = Insert(nodes, i, end, (end - i) / 2 + 1); 
    }
    // 在 medians 中递归调用 Select1，找到中值的中值
    return Select1(medians, 0, m_index - 1, (m_index + 1) / 2);
}

// 查找数组 nodes 中第 k 小的元素，返回该元素
Node Select1(vector<Node>& nodes, int left, int right, int k) {
    if (left == right) // 单元素
        return nodes[left];
    Node m_Medians = findMedian(nodes, left, right); // 查找中位数的中位数
    int pivot = Partition2(nodes, left, right, m_Medians); // 以 m_Medians 为主元进行划分
    int index = pivot - left + 1; // 计算主元在子数组中的位置
    if (k == index) 
        return nodes[pivot]; 
    else if (k < index) // 此时，向左递归（k 在左半边）
        return Select1(nodes, left, pivot - 1, k); 
    else // 否则递归右半部分
        return Select1(nodes, pivot + 1, right, k - index); 
}

查找带权中位数

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
// 查找带权中位数，wM_Position 表示所需加权中位数位置（0.5 表示中位数）
Node Select2(vector<Node>& nodes, int left, int right, double wM_position) {
    if (left == right) // 单元素
        return nodes[left]; 
    Node m_Median = findMedian(nodes, left, right); // 查找中位数组的中位数
    int pivot = Partition2(nodes, left, right, m_Median); // 划分的主元下标
    double L_Sum = 0; // 左侧元素权重和
    for (int j = left; j < pivot; j++) 
        L_Sum += nodes[j].weight;

    // 判断累加权重是否满足条件
    if (L_Sum < wM_position && L_Sum + nodes[pivot].weight >= wM_position) 
        return nodes[pivot];
    else if (L_Sum >= wM_position) // 累加权重大于等于 wM_position，向左递归
        return Select2(nodes, left, pivot - 1, wM_position);
    else // 否则向右递归
        return Select2(nodes, pivot + 1, right, wM_position - L_Sum - nodes[pivot].weight);
}

void WeightMedian(int length, vector<int> num, vector<double> weight, int index) {
    vector<Node> nodes(length); // 初始化节点数组
    for (int i = 0; i < length; i++) {
        nodes[i].value = num[i];
        nodes[i].weight = weight[i]; 
    }
    cout << Select2(nodes, 0, length - 1, 0.5).value << endl; // 输出带权中位数的值
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
	int length = 2;
	vector<int> num = {1, 2};
	vector<double> weight = {0.4, 0.6};
	cout << "Length: " << length << endl;
	
	cout << "num: ";
	for (int i = 0; i < length; i++)
		cout << num[i] << " ";
	cout << endl;
	
	cout << "weight: ";
	for (int i = 0; i < length; i++)
		cout << weight[i] << " ";
	cout << endl;
	
	cout << "The weight median is: ";
	WeightMedian(length, num, weight, 0);
	return 0;
}

实例测试

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
/*
实例1：
输入：
length = 10;
num = {13825, 28995, 18417, 92445, 86407, 90546, 46896, 14757, 89837, 18252}; 
weight = {0.08720404, 0.09585595, 0.12070109, 0.02521966, 0.01221968, 0.12648725, 0.13076193, 0.19128049, 0.15673069, 0.05353921};
输出：
28995

实例2：
输入：
length = 1;
num = {1};
weight = {1.0};
输出：
1

实例3：
输入：
length = 5;
num = {1, 5, 3, 2, 4};
weight = {0.45, 0.1, 0.1, 0.1, 0.25};
输出：
2

实例4：
输入：
length = 2;
num = {1, 2};
weight = {0.4, 0.6};
输出：
2
*/

运行结果

实例1
实例2 实例3 实例4
提交界面
个人学习笔记 > 算法设计与分析
#算法
算法设计与分析-Lab01
http://dbqdss.github.io/2024/10/05/算法设计与分析/算法设计与分析-Lab01/
作者
DBQDSS
发布于
2024年10月5日
许可协议