class Solution {
public:
int GetUglyNumber_Solution(int index) {
if ( index <= 0 ) return 0 ;
int count = 0 ;
int sumOfUgly = 0 ;
while ( sumOfUgly <= index ) {
count += 1 ;
if ( isUgly( count ) ) {
sumOfUgly++ ;
}
}
return count ;
}
bool isUgly( int n ) {
while ( n % 2 == 0 ) {
n /= 2 ;
}
while ( n % 3 == 0 ) {
n /= 3 ;
}
while ( n % 5 == 0 ) {
n /= 5 ;
}
return n == 1 ? true : false ;
}
};复杂版就要用指针控制了，其实思路也不复杂，以空间换时间。class Solution {
public:
int GetUglyNumber_Solution(int index) {
if ( index <= 0 ) return 0 ;
int* arr = new int[index] ;
arr[0] = 1 ;
int* multi2 = arr ;
int* multi3 = arr ;
int* multi5 = arr ;
int nextIndex = 1 ;
while ( nextIndex < index ) {
int min = MIN( (*multi2) * 2, (*multi3) * 3, (*multi5) * 5 ) ;
arr[nextIndex] = min ;
while ( *multi2 * 2 <= min ) multi2++ ;
while ( *multi3 * 3 <= min ) multi3++ ;
while ( *multi5 * 5 <= min ) multi5++ ;
nextIndex++ ;
}
int result = arr[nextIndex - 1] ;
if ( arr != NULL ) delete[] arr ;
return result ;
}
int MIN( int n1, int n2, int n3 ) {
int tmp = n1 < n2 ? n1 : n2 ;
return tmp < n3 ? tmp : n3 ;
}
};有两个地方要注意：int result = arr[nextIndex - 1] ;
int result = arr[nextIndex - 1] ;是错误的，nextIndex要回退一个步长。
if ( arr != NULL ) delete[] arr ;
if ( multi2 != NULL ) delete multi2 ;
if ( multi3 != NULL ) delete multi3 ;
if ( multi5 != NULL ) delete multi5 ;这四个指针指向的同一个内存空间if ( arr != NULL ) delete[] arr ;已经归还了内存，但是我还delete了multi2、multi3、multi5，导致同一块内存释放了三次，这无法通过编译。
原文：http://blog.csdn.net/chengonghao/article/details/51355852