一步步学算法(算法例题)-1
发布时间: 2013-09-08 15:21:21 作者: rapoo
一步步学算法(算法题解)---1
本人大二,最近开始自学算法,在此记录自己学习过程中接触的习题。与君共勉。
水平有限,目前涉及的题目都比较水。
题目分布为5+1. 5为自己学习的5道水题。 1为从网上找到的比较有水平的相关题目。
一步步学算法(算法题解)---1
数值处理相关问题。
1。19头牛int GetUglyNumber_Solution2(int index){ 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 Min(int number1, int number2, int number3){ int min = (number1 < number2) ? number1 : number2; min = (min < number3) ? min : number3; return min;}
和第一种思路相比,这种算法不需要在非丑数的整数上做任何计算,因此时间复杂度要低很多。感兴趣的读者可以分别统计两个函数GetUglyNumber_Solution1(1500)和GetUglyNumber_Solution2(1500)的运行时间。当然我们也要指出,第二种算法由于要保存已经生成的丑数,因此需要一个数组,从而需要额外的内存。第一种算法是没有这样的内存开销的。