313. Super Ugly Number

public class Solution {
    public int NthSuperUglyNumber(int n, int[] primes) {
        int[] ugly_numbers = new int[n];
        int[] indices = new int[primes.Length];
        int[] next_ugly = (int[])primes.Clone();
        ugly_numbers[0] = 1;
        
        for (int i = 1; i < n; i++) {
            int next_val = next_ugly.Min();
            ugly_numbers[i] = next_val;
            
            for (int j = 0; j < primes.Length; j++) {
                if (next_val == next_ugly[j]) {
                    indices[j]++;
                    next_ugly[j] = ugly_numbers[indices[j]] * primes[j];
                }
            }
        }
        
        return ugly_numbers[n - 1];
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int>& ugly_numbers = new int[n];
        vector<int>& indices = new int[primes.size()];
        vector<int>& next_ugly = (int[])primes.Clone();
        ugly_numbers[0] = 1;
        
        for (int i = 1; i < n; i++) {
            int next_val = next_ugly.Min();
            ugly_numbers[i] = next_val;
            
            for (int j = 0; j < primes.size(); j++) {
                if (next_val == next_ugly[j]) {
                    indices[j]++;
                    next_ugly[j] = ugly_numbers[indices[j]] * primes[j];
                }
            }
        }
        
        return ugly_numbers[n - 1];
    }
}

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly_numbers = new int[n];
        int[] indices = new int[primes.length];
        int[] next_ugly = primes.clone();
        ugly_numbers[0] = 1;
        
        for (int i = 1; i < n; i++) {
            int next_val = Arrays.stream(next_ugly).min().getAsInt();
            ugly_numbers[i] = next_val;
            
            for (int j = 0; j < primes.length; j++) {
                if (next_val == next_ugly[j]) {
                    indices[j]++;
                    next_ugly[j] = ugly_numbers[indices[j]] * primes[j];
                }
            }
        }
        
        return ugly_numbers[n - 1];
    }
}

var nthSuperUglyNumber = function(n, primes) {
    let ugly_numbers = [1];
    let indices = new Array(primes.length).fill(0);
    let next_ugly = primes.slice();
    
    for (let i = 1; i < n; i++) {
        let next_val = Math.min(...next_ugly);
        ugly_numbers.push(next_val);
        
        for (let j = 0; j < primes.length; j++) {
            if (next_val === next_ugly[j]) {
                indices[j]++;
                next_ugly[j] = ugly_numbers[indices[j]] * primes[j];
            }
        }
    }
    
    return ugly_numbers[n - 1];
};

func nthSuperUglyNumber(n int, primes []int) int {
    ugly_numbers := make([]int, n)
    ugly_numbers[0] = 1
    indices := make([]int, len(primes))
    next_ugly := append([]int(nil), primes...)
    
    for i := 1; i < n; i++ {
        next_val := min(next_ugly)
        ugly_numbers[i] = next_val
        
        for j := 0; j < len(primes); j++ {
            if next_val == next_ugly[j] {
                indices[j]++
                next_ugly[j] = ugly_numbers[indices[j]] * primes[j]
            }
        }
    }
    
    return ugly_numbers[n-1]
}

func min(arr []int) int {
    minVal := arr[0]
    for _, val := range arr {
        if val < minVal {
            minVal = val
        }
    }
    return minVal
}

Algorithm

Инициализация

Создайте массив ugly_numbers длиной n для хранения супер некрасивых чисел. Создайте массив indices длиной primes для отслеживания позиций в массиве ugly_numbers. Создайте массив next_ugly длиной primes для хранения следующего возможного супер некрасивого числа для каждого простого числа из primes.

Генерация супер некрасивых чисел

Установите первое значение в ugly_numbers как 1. Повторяйте до тех пор, пока не заполните массив ugly_numbers: Найдите минимальное значение в массиве next_ugly и добавьте его в ugly_numbers. Обновите соответствующий индекс в indices и пересчитайте значение в next_ugly.

Возврат результата

Верните последнее значение в массиве ugly_numbers, которое будет n-м супер некрасивым числом.

😎