Sword finger offer 49 Ugly number (three finger needling technique)

One 、263. Ugly number

263. Ugly number

class Solution {
    
public:
    bool isUgly(int n) {
    
        if(n <= 0){
    
            return false;
        }
        while(n % 2 == 0){
    
            n >>= 1;
        }
        while(n % 3 == 0){
    
            n /= 3;
        }
        while(n % 5 == 0){
    
            n /= 5;
        }
        return n == 1;
    }
};

Two 、264. Ugly number II

264. Ugly number II

1. Three finger needling

class Solution {
    
public:
    int nthUglyNumber(int n) {
    
        int idx2 = 0;
        int idx3 = 0;
        int idx5 = 0;
        vector<int> nums(n, 0);
        nums[0] = 1;  //  The first ugly number is 1

        for(int i = 1; i < n; i++){
    
        	//  Generate new ugly numbers from the ugly numbers in the array , Store the smallest ugly number in the array 
            nums[i] = min(nums[idx2] * 2, min(nums[idx3] * 3, nums[idx5] * 5));
            //  Which is from idx Generate new ugly numbers , Which one? idx Move back , Used for the next generation of ugly numbers 
            //  Three if Juxtaposition , Used to remove heavy 
            if(nums[i] == nums[idx2] * 2){
    
                idx2++;
            }
            if(nums[i] == nums[idx3] * 3){
    
                idx3++;
            }
            if(nums[i] == nums[idx5] * 5){
    
                idx5++;
            }
        }
        return nums[n-1];
    }
};

2. set Sorting and de duplication

set Can sort , We use it set Save the generated ugly numbers , Take the smallest ugly number and multiply it by 2、3、5 You can get a new ugly number , Deposit in set Auto sort after , The first n Round robin deletes the smallest ugly number , This is the first n Ugly number

class Solution {
    
public:
	int nthUglyNumber(int n) {
    
        set<double> s;  // set  Is ordered , And not repeated 
        double answer = 1;
        for (int i = 1; i < n; i++) {
    
            s.insert(answer * 2);
            s.insert(answer * 3);
            s.insert(answer * 5);
            answer = *s.begin();
            s.erase(answer);
        }
        return answer;
    }	
};