算法思路

  • 多路归并可以看做归并算法的延伸
  • 假设我们有m个需要归并的已经排好序的序列，我们需要求合并后的数组，或者合并后数组的多少位，这种时候我们需要用多路归并算法

  • 多路归并算法的思想就是，有m个指针分别指向序列的起始位置，然后我比较m个数，选出m个数中的最小值，然后把该最小值对应的序列指针往后挪一位，直到算法结束

    Acwing. 62 丑数

    题目描述

    我们把只包含质因子2、3和5的数称作丑数（Ugly Number）
    例如6、8都是丑数，但14不是，因为它包含质因子7
    求第n个丑数的值

    算法实现

  • 这里的多路归并是2丑数序列，3丑数序列和5*丑数序列的多路归并

    1. class Solution {
    2. public:
    3.   int getUglyNumber(int n) {
    4.       int i = 0, j = 0, k = 0, cnt = n;
    5.       vector<int> ugly_number;
    6.       ugly_number.push_back(1);
    7.       while (cnt --) {
    8.           if (ugly_number[i] * 2 <= ugly_number[j] * 3 && ugly_number[i] * 2 <= ugly_number[k] * 5) {
    9.               ugly_number.push_back(ugly_number[i] * 2);
    10.           } else if (ugly_number[j] * 3 <= ugly_number[i] * 2 && ugly_number[j] * 3 <= ugly_number[k] * 5) {
    11.               ugly_number.push_back(ugly_number[j] * 3);
    12.           } else {
    13.               ugly_number.push_back(ugly_number[k] * 5);
    14.           }
    16.           if (ugly_number.back() % 2 == 0) {
    17.               i ++;
    18.           }
    20.           if (ugly_number.back() % 3 == 0) {
    21.               j ++;
    22.           }
    24.           if (ugly_number.back() % 5 == 0) {
    25.               k ++;
    26.           }
    27.       }
    28.       return ugly_number[n - 1];
    29.   }
    30. };