My easy-to-follow C++ solution


  • 0
    J
    int nthUglyNumber1(int n) // Score 16ms
    {
    	int result = 1; // For the case n = 1
    	if (n > 1)
    	{
    		vector<int> u(n,0);
    		u[0] = 1;
    
    		int c1,c2,c3; // 3 candidates corresponding to the three factors 2, 3, 5
    		int i1 = 0, i2 = 0, i3 = 0;
    		int a[3] = {2,3,5};
    		c1 = a[0]*u[i1]; c2 = a[1]*u[i2]; c3 = a[2]*u[i3]; // 3 candidates, initialized
    
    		int i,j,cmin;
    		for (i = 1; i < n; i++)
    		{
    			// Find the minimum from c2, c3, c5
    			cmin = c1; j = a[0]; // 2
    			if (cmin > c2) { cmin = c2; j = a[1]; } // 3
    			if (cmin > c3) { cmin = c3; j = a[2]; } // 5
    			while (cmin == u[i-1]) // Checking this condition is to prevent duplication
    			{
    				// Update one of the three candidates
    				if (j == a[0]) { i1++; c1 = a[0]*u[i1]; }
    				if (j == a[1]) { i2++; c2 = a[1]*u[i2]; }
    				if (j == a[2]) { i3++; c3 = a[2]*u[i3]; }
    				// Find the minimum from c2, c3, c5 again
    				cmin = c1; j = a[0]; // 2
    				if (cmin > c2) { cmin = c2; j = a[1]; } // 3
    				if (cmin > c3) { cmin = c3; j = a[2]; } // 5
    			}
    			
    			u[i] = cmin;
    		}
    		result = u[n-1];
    	}
    
    	return (result);
    }

  • 0
    L

    I do not understand why it could not come out this situation that given x, y, z, x2 for example is the smallest, but x2 was already in the vector?
    Could you please explain this for me?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.