- 题意:找出以某些数为公因数的 递增排序的第n个数
- 条件:indexes 维护了 primes的元素的相乘因素(uglies)的index。
- 思路:每次从 primes的遍历*中,找出最小的一个ugly,添加到uglies中去,然后将 indexes维护的primes的相乘对象的索引表中,找出这个,+1.
- 应用: 每次只变动一个数的思想。 相乘时候,遍历primes是循环进行的。 相乘的对象 是 primes的各个元素,也是uglies中的所有元素。由于是最小值,所以每次保留最小的。 每次找出 得到最小值的prime的index,+1,方便下次迭代。问题转化, primeprime==》多次迭代,变成 uglyprime, 处理对象变了。每个prime每次*的对象,有可能反复是同一个数,所以用indexes记录走到的位置。避免重复。不重复的思想:找出重复计算的地方,找出不重复计算的方法,用极值约束,index加以记录。
- 没有找到思路原因: 没有将问题建模,抽象为 prime*ugly 的迭代过程+每次一个最小值的比较。 索引记录prime的迭代位置。
class Solution: def nthSuperUglyNumber(self, n, primes): uglies=[1] indexes=[0]*len(primes) while len(uglies)