• ``````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);
}``````

• 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?

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