雪糕239_leetcode 全排列

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的最大数量。

注意：Tony 可以按任意顺序购买雪糕。

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。

菜鸟新手刚入leetcode刷题，也是刚进csdn写博客，有不足之处还请大佬们多多指教

对于这个题乍一眼我就下意识想着用动态规划dp求解了，以看很明显的就是简单的背包问题，于是我立马的就开始写出了dp摸板并跑了几个实例，然后提交，慢慢期待，没想到结果却被一组大数据给卡了超时了，下面我将把超时数据贴下

[282,1834,280,912,386,1900,1367,1242,369,745,1977,807,275,1987,1314,142,1338,1637,332,908,1402,542,287,962,1292,1180,1482,1690,2,1060,88,1122,401,1704,1792,1539,1938,612,1905,1592,582,1784,82,664,261,770,934,1422,902,1981,447,1385,1418,370,118,486,1117,1530,1058,618,1945,574,818,134,1277,1338,754,282,1399,1433,1191,1436,1202,918,1757,450,1342,767,606,1846,647,1650,624,448,50,1722,1002,943,1220,1795,742,626,1802,1179,1274,1542,152,1282,963,1776,1970,1738,696,136,804,1902,1202,621,534,262,919,430,702,1843,1947,1847,1982,1830,888,1492,1905,786,1157,874,1624,562,418,498,1144,830,1931,1802,497,514,1708,1002,462,1514,890,782,172,1680,34,331,372,302,120,416,1608,1420,1702,842,252,1207,1735,1924,1862,6,1076,1042,1186,1922,1762,1661,1490,1727,266,142,672,496,1062,1592,166,1097,1988,802,1566,1514,1099,358,572,878,102,478,568,343,1298,1556,1562,1968,1583,416,762,30,18,570,482,942,1922,1772,1477,508,1613,2001,1554,578,1726,34,747,1815,778,1202,1517,92,1387,422,120,1134,922,1106,1908,119,404,1890,1395,1787,850,482,1230,1280,1497,1250,761,314,1018,725,124,939,1185,1742,342,114,1344,1702,1896,494,242,1958,1861,1850,627,1872,611,1730,101,386,786,971,1980,215,298,1835,1957,22,1026,1388,1502,79,1810,1877,1217,1874,1807,1999,1925,1576,412,1567,834,1078,1346,722,1206,227,178,1796,836,1506,542,1097,1770,338,282,836,479,992,1847,1812,667,1852,1722,1248,1248,778,282,1340,1087,22,1285,456,402,260,1106,332,342,1797,408,738,702,175,503,1130,1510,722,1410,682,442,1538,756,562,142,682,1986,1586,294,493,454,1802,770,1734,1055,1217,512,449,834,1310,1762,1182,47,984,1530,784,1866,1910,362,500,1570,1542,1482,1330,702,1722,661,53,1822,1202,422,1300,160,222,1494,650,1774,738,552,1417,1049,1522,1066,1817,1242,715,482,162,188,975,82,1726,1860,157,1234,438,764,1414,567,1442,1126,1022,727,34,1251,1458,1732,1108,1938,178,1747,147,697,706,1282,206,594,317,1720,882,1802,938,1947,612,782,1666,812,1815,1704,682,1298,1738,876,1131,1540,161,627,945,1952,1635,742,878,1507,1642,1152,258,902,1014,402,1446,1607,1978,1313,734,858,977,552,1654,1602,870,1450,298,342,325,858,1022,1510,1687,1302,777,1664,218,1652,834,325,1746,1219,1968,62,632,718,942,780,2,1110,1947,1302,1862,238,1000,520,762,578,602,122,1181,132,604,42,526,1122,210,1208,794,530,370,1768,1441,712,737,108,1154,1268,1813,1713,720,1946,547,466,465,134,1762,582,1402,1660,2,923,946,1872,1502,586,1696,1354,1374,322,24,811,463,1510,437,282,1705,1582,1390,1282,621,896,1186,1247,342,180,425,1046,1162,1314,1738,502,1882,968,1094,1580,585,1252,912,1142,1042,1042,2,202,767,1343,1046,1042,1467,1082,1715,268,459,1602,1502,1690,302,1954,1016,1306,1982,342,877,1366,917,1002,524,1327,866,1512,1018,253,1756,1117,1276,358,1237,1486,1622,854,1306,1778,1802,1442,202,1002,1992,966,1297,1989,1774,22,332,352,288,359,310,692,312,1407,439,1167,998,1852,1618,1041,1884,264,590,430,142,1140,1652,156,938,1686,670,1578,156,1042,1680,1102,942,1442,1202,1842,525,1682,60,1447,1716,754,402,358,292,1592,214,563,1053,1309,654,1874,1322,1725,1644,690,20,1692,1232,92,1842,1498,775,1088,754,162,783,632,1973,1010,802,1252,722,57,1850,142,1802,84,1952,762,1482,1202,667,398,11,536,1797,1412,338,166,958,983,1504,1067,1797,66,1527,829,952,53,22,966,1830,308,80,274,1393,632,454,777,186,1002,2,1542,1186,1534,1266,1796,647,969,360,806,978,292,402,1029,1442,1368,1278,1752,122,1354,568,37,1452,1224,674,450,1206,1405,1016,2,1634,697,427,1211,710,573,208,412,1900,554,395,1252,752,1637,542,258,574,518,1794,891,963,106,14,783,976,1648,122,1742,962,557,1992,1022,1776,6,985,1058,743,1452,1872,1060,427,242,1208,402,882,76,158,1941,256,1922,1000,1170,1977,50,1203,880,559,46,1727,762,286,1746,1782,638,1717,1142,602,1952,1383,1409,692,335,290,386,1326,221,1901,1470,1064,981,257,148,1890,42,1288,1928,195,791,1252,1898,1695,470,696,1220,1873,1190,1088,889,1930,112,1969,996,422,78,1228,1636,781,802,1430,810,512,677,350,1188,1608,726,844,1465,1325,1648,910,1122,1896,1902,653,1826,1586,1382,440,1068,562,1066,1546,622,94,1328,737,246,922,1018,1678,1802,1102,1960,1922,682,306,1750,1708,1163,972,1913,1722,482,589,1169,431,623,392,142,1443,134,638,1602,1842,518,1422,526,1074,383,1846,1512,1224,256,897,1956,1060,972,421,502,1878,1980,1970,1691,1947,730,1507,1130,1320,738,1133,4,846,102,221,952,1587,1342,1300,1283,1786,850,905,180,26,1647,750,46,1988,122,756,1177,1524,1603,1960,242,536,82,1942,1569,243,1268,562,238,1314,880,395,2,1386,674,1717,538,1842,50,1010,802,1902,572,898,952,1624,1250,1682,432,501,832,490] 767081

和我的dp超时代码如下：

仔细以看原来数据规模是10的5次方，而dp的话时间复杂度是n方的时间复杂度，所以超时了，dp是不适用这个题了，因此只能另寻他法，使用先排序在贪心，这个思路的主要时间复杂度在于排序的那部分，排序的话需要O nlog(n)的时间复杂度对于这个10的5次方的数据来说是能够过的，贪心的话只需要O（n）的时间复杂度,综合这个思路就是O nlog(n)的时间复杂度，空间复杂度是O（1），然后试了写一下代码如下: