• 数据结构与算法之堆: Leetcode 313. 超级丑数 (Typescript版)


    超级丑数

    • https://leetcode.cn/problems/super-ugly-number/

    描述

    • 超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 primes 中。
    • 给你一个整数 n 和一个整数数组 primes ,返回第 n 个 超级丑数 。
    • 题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

    示例 1

    输入:n = 12, primes = [2,7,13,19]
    输出:32 
    解释:给定长度为 4 的质数数组 primes = [2,7,13,19],前 12 个超级丑数序列为:[1,2,4,7,8,13,14,16,19,26,28,32] 。
    
    • 1
    • 2
    • 3

    示例 2

    输入:n = 1, primes = [2,3,5]
    输出:1
    解释:1 不含质因数,因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
    
    • 1
    • 2
    • 3

    提示

    • 1 <= n <= 1 0 5 10^5 105
    • 1 <= primes.length <= 100
    • 2 <= primes[i] <= 1000
    • 题目数据 保证 primes[i] 是一个质数
    • primes 中的所有值都 互不相同 ,且按 递增顺序 排列

    算法实现

    • 首先要了解下质数
      • 又称素数,有无限个
      • 质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数
    • 再看下质因数
      • 是一个数的约数,并且是质数
    • 再次要了解丑数
      • 只包含因子2,3,5的正整数被称为丑数,比如4,10,12都是丑数,而7,23,111则不是丑数,另外1也是丑数
    • 超级丑数
      • 和丑数不是一回事
      • 是指所有质因数都是长度为k的质数列表primes中的正整数

    1 )将问题分而治之

    class Ugly {
      n: number = 0;
      primes: number[] = [];
      constructor (n: number, primes: number[]) {
        this.n = n;
        this.primes = primes;
      }
      // 获取第n个超级丑数,本质是一个查询操作
      getNthUg() {
        const res = [1]; // 超级丑数列表
        let i = 2; // 从2开始找
        const { primes, n } = this;
        while (res.length < n) {
          const arr = Ugly.getPrimes(i); // 获取当前i的所有质因数列表
          const l = arr.length; // 质因数列表长度的
          let j = 0; // 指针往上数
          // 遍历当前i的所有质因数找到和primes列表中匹配的质因数, 有一个不匹配都算失败
          for (; j < l; j++) {
            // 匹配不到则退出
            if (!primes.find(item => item === arr[j])) break;
          }
          // 这时候上面的for循环遍历完成, 而且当前i的所有质因数都匹配成功, 就可以进行下一步的操作
          if (j === l) {
            (l === 0) && primes.find((item) => item === i) && res.push(i); // 当前没有质因数(上面for不会执行),但是当前的i在给定列表中,存储i(满足超级丑数)
            (l !== 0) && res.push(i); // 当前i存在质因数列表时,存储 i(满足超级丑数)
          }
          i++; // i 递增
        }
        return res[n - 1]; // 获取第n个
      }
      // 计算指定正整数n的质因数
      static getPrimes (n) {
        const prime = (n) => {
          const arr = []; // 存储所有的质因数
          for (let i = 2; i <= n / 2; i++) {
            if (n % i === 0 && !prime(i).length) arr.push(i); // 这里有一个递归找质因数
          }
          return arr;
        }
        return prime(n);
      }
    }
    
    function nthSuperUglyNumber(n: number, primes: number[]): number {
      const ugly = new Ugly(n, primes);
      return ugly.getNthUg();
    };
    
    • 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
    • 47
    • 思路:
      • 给定任意整数,算出其质因数
      • 质因数是否在指定质因数范围内
      • 是否达到指定个数 n
    • 干扰点:丑数和超级丑数不是一回事
    • 正整数的质因数的算法
      • 如果这个正整数是n, 它的因数(约数)的范围一定在 [2, n/2]
      • 当然这个 n/2 可能不是整数,但是范围就在这儿
      • 先判断是否是因数: n能被i整除
      • 质因数:不仅要满足是因数,而且都是质数(除了1和它本身没有其他因数)
      • 质数如何解决呢,这里就用到了递归,如果整数后找不到其他因数,则本身就是质数
      • 这里 !prime(i).length 是判断质数的关键
    • 还要注意 getNthUg 方法中的查询操作,这是一个循规蹈矩的做法,但是性能很低
      • 性能瓶颈在,查找两个数组的方法
      • 目前在 第 77 个 case 的时候, 提示:超出时间限制
      • 我们需要提升查找效率

    2 )使用堆结构来提升查找性能,优化版

    class Ugly {
      n: number = 0;
      primes: MaxHeap;
      constructor (n: number, primes: number[]) {
        this.n = n;
        this.primes = new MaxHeap(primes);
      }
      // 获取第n个超级丑数,本质是一个查询操作
      getNthUg() {
        const res = [1];
        let i = 2; // 从2开始找
        const { primes, n } = this;
        while (res.length < n) {
          const arr = Ugly.getPrimes(i); // 获取当前i的所有质因数列表
          const l = arr.length; // 质因数列表长度的
          let j = 0; // 指针往上数
          // 遍历当前i的所有质因数找到和primes列表中匹配的质因数, 有一个不匹配都算失败
          for (; j < l; j++) {
            // 匹配不到则退出
            if (!primes.find(arr[j])) break;
          }
          // 这时候上面的for循环遍历完成, 而且当前i的所有质因数都匹配成功, 就可以进行下一步的操作
          if (j === l) {
            (l === 0) && primes.find(i) && res.push(i); // 当前没有质因数(上面for不会执行),但是当前的i在给定列表中,存储i(满足超级丑数)
            (l !== 0) && res.push(i); // 当前i存在质因数列表时,存储 i(满足超级丑数)
          }
          i++; // i 递增
        }
        return res[n - 1]; // 获取第n个
      }
      // 计算指定正整数n的质因数
      static getPrimes (n) {
        const prime = (n) => {
          const arr = []; // 存储所有的质因数
          for (let i = 2; i <= n / 2; i++) {
            if (n % i === 0 && !prime(i).length) arr.push(i); // 这里有一个递归找质因数
          }
          return arr;
        }
        return prime(n);
      }
    }
    
    class MaxHeap {
      heap: number[] = [];
      max: number = 0;
      constructor (arr) {
        this.heap = arr;
        this.max = arr.length;
        this.sort();
      }
      sort () {
        const iArr = this.heap;
        const n = iArr.length;
        if (n <= 1) return iArr;
        for (let i = Math.floor(n / 2); i >= 0; i--) {
          MaxHeap.maxHeapify(iArr, i, n);
        }
        return iArr;
      }
      // 交换两个元素
      static swap (arr, i, j) {
        if (i === j) return;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
      // 构建最大堆的过程
      static maxHeapify (Arr, i, size) {
        // 左节点(索引)
        const l = i * 2 + 1;
        // 右节点
        const r = i * 2 + 2;
        let largest = i;
        // 父节点i和左节点l做比较取最大
        if (l <= size && Arr[l] > Arr[largest]) largest = l;
        // 右节点和最大值比较
        if (r <= size && Arr[r] > Arr[largest]) largest = r;
        if (largest !== i) {
          MaxHeap.swap(Arr, i, largest)
          MaxHeap.maxHeapify(Arr, largest, size)
        }
      }
      find (val, i = 0) {
        const arr = this.heap;
        if (val > arr[i] || i > this.max) return false;
        if (val === arr[i]) return val;
        return this.find(val, i * 2 + 1) || this.find(val, i * 2 + 2);
      }
    }
    
    function nthSuperUglyNumber(n: number, primes: number[]): number {
      const ugly = new Ugly(n, primes);
      return ugly.getNthUg();
    };
    
    • 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
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 使用堆结构,取代普通数组结构,让查找效率提升 O(n) => O(logn)
    • 但是这里仍有大量递归运算,消耗太多性能
    • 同样,在第77个case时出现了提示:超出时间限制

    3 )使用动态规划

    function nthSuperUglyNumber (n: number, primes: number[]) {
        const dp = new Array(n + 1).fill(0);
        const m = primes.length;
        const pointers = new Array(m).fill(0);
        const nums = new Array(m).fill(1);
        for (let i = 1; i <= n; i++) {
            let minNum = Number.MAX_SAFE_INTEGER;
            for (let j = 0; j < m; j++) {
                minNum = Math.min(minNum, nums[j]);
            }
            dp[i] = minNum;
            for (let j = 0; j < m; j++) {
                if (nums[j] == minNum) {
                    pointers[j]++;
                    nums[j] = dp[pointers[j]] * primes[j];
                }
            }
        }
        return dp[n];
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 这是官方做法, 动态规划解决了递归的问题,由递归变成了递推
    • 时间复杂度 O(nm) ≈ O( n 2 n^2 n2)
  • 相关阅读:
    创建 SAP Fiori Catalog 时遇到的 duplicate 记录的问题分析
    LibTorch之网络模型构建
    frp隧道(流量代理)
    OPPO/真我手机ColorOS13系统解账户锁-移除手机密码图案锁方法
    git学习笔记之用命令行解决冲突
    c++征途 --- 类和对象 --- 友元
    Kotlin高仿微信-第8篇-单聊
    rust学习(tokio协程分析一)
    Maven——maven核心概念
    Python接口自动化测试自学路线
  • 原文地址:https://blog.csdn.net/Tyro_java/article/details/133625091