程序员面试题精选100题(37)-寻找丑数(一种新的排序方法)

// 程序员面试题精选100题(37)-寻找丑数.cpp : 定义控制台应用程序的入口点。
//
/*
main idea is how sort ugly number ,it is impossible to sort the ugly one by one in regular method, so the sort method in the array is a good idea,which sacrifice the space in exchange for the time
*/
#include "stdafx.h"
#include <iostream>
using namespace std;
int minofthree(int n1,int n2,int n3)
{
	if (n1>n2)
	{
		if (n2>n3)
		{
			return n3;
		}
		else
			return n2;
	}
	else
	{
		if (n1>n3)
		{
			return n3;
		}
		else
			return n1;
	}
}


int Min(int number1, int number2, int number3)
{
	int min = (number1 < number2) ? number1 : number2;
	min = (min < number3) ? min : number3;

	return min;
}
int GetUglyNumber_Solution2(int index)// other's answer
{
	if(index <= 0)
		return 0;

	int *pUglyNumbers = new int[index];
	pUglyNumbers[0] = 1;
	int nextUglyIndex = 1;

	int *pMultiply2 = pUglyNumbers;
	int *pMultiply3 = pUglyNumbers;
	int *pMultiply5 = pUglyNumbers;

	while(nextUglyIndex < index)
	{
		int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);
		pUglyNumbers[nextUglyIndex] = min;

		while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])
			++pMultiply2;
		while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])
			++pMultiply3;
		while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])
			++pMultiply5;

		++nextUglyIndex;
	}

	int ugly = pUglyNumbers[nextUglyIndex - 1];
	delete[] pUglyNumbers;
	return ugly;
}


int _tmain(int argc, _TCHAR* argv[])
{
	int index=3,i2,i3,i5,currmax,s2=0,s3=0,s5=0;//s2 means when finding the first value which is greater than currmax,  for loop start froms2
	int *uglynum=new int[1500];
	uglynum[0]=1;uglynum[1]=2;uglynum[2]=3;
	int M2,M3,M5;
	currmax=3;
	while(index<1500)
	{
		for(i2=s2;i2<1500;i2++)
		{
			if (uglynum[i2]*2>currmax)//the first value which bigger than currmax
			{
				s2=i2;//next time from this on
				break;
			}
		}
		M2=uglynum[i2]*2;

		for(i3=s3;i3<1500;i3++)
		{
			if (uglynum[i3]*3>currmax)
			{
				s3=i3;//next time from this on
				break;
			}
		}
		M3=uglynum[i3]*3;

		for(i5=s5;i5<1500;i5++)
		{
			if (uglynum[i5]*5>currmax)
			{
				s5=i5;//next time from this on because next currmax must be greater than current currmax
				break;
			}
		}
		M5=uglynum[i5]*5;

		uglynum[index]=minofthree(M2,M3,M5);
		currmax=uglynum[index];
		index++;
	}
	for (int i=0;i<15;i++)
	{
		cout<<uglynum[i]<<" ";
	}
	cout<<endl;
	for (int ii=1;ii<=15;ii++)
	{
		cout<<GetUglyNumber_Solution2(ii)<<" ";
	}	
	delete[] uglynum;
	system("pause");
	return 0;
}