作者:金花婆婆2502921867 | 来源:互联网 | 2023-02-01 23:12
题目Givenalistofnonnegativeintegers,arrangethemsuchthattheyformthelargestnumber.For
题目
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9]
, the largest formed number is 9534330
.
Note: The result may be very large, so you need to return a string instead of an integer.
原题链接: https://oj.leetcode.com/problems/largest-number/
算法分析
case1(一般情况):
[3, 30, 34, 5, 9] -> (9 -> 5 -> 34 -> 3 -> 30) -> 9534330
直观想法按位从高到底排序
可以很容易得到9->5的顺序,然而接下来问题来了,位相等的情况怎么办?
考虑3,30,34(数字组1)
简单考虑[3, 30],显然3->30要比30->3的值更大,即3>30的个位0;
再考虑[3, 34],(34->3) > (3->34),即34的个位4>3;
最后[30, 34],34 > 30;
所以数字组1的排序为34->3->30;
最终结果为9->5->34->3->30
case2(不止一位相等,多位高位相等的情况):
[824, 8247] -> (824 -> 8247) -> 8248247
逐一从高位到低位比较,那么第二个数字的最低位7应该与第一个数字的哪位比较呢?决定这两数顺序的不外乎,824->8247,8247->824这两种情况,直观上7应与第一个数字的第一位8比较,由于7<8,所以824->8247
case3 (不止一位相等,多位高位相等的情况):
[824, 82483] -> (82483 -> 824) -> 82483824
case4(重复数字):
[33, 333] -> 33333
一般考虑假设待比较的数字为a1a2, b1b2b3,a1b1…均为位;在重复数字的情况下
如
a1 a2
|| ||
b1 b2 b3
且b3 == a1,b1 == a2,此时可以得到b1 == a1 == a2 == b2 == b3,即全等,因此最大的比较次数为数字1的位数加数字2的位数 - 1次,该例子的情况为4次。
题目陷阱
case1(有数字为0):
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
case2(数字均为0):
[0, 0]
算法设计
Integer类,将int按位存储,next取出下一位方法;
1 class Integer {
2 public:
3 Integer(int i);
4
5 int getCount() { return count; }
6
7 int next() {
8 if (!tmp_count) {
9 tmp_count = count;
10 }
11 return digits[--tmp_count];
12 }
13
14 private:
15 int _i;
16 int count;
17 int tmp_count;
18 int digits[10];
19 };
20
21 Integer::Integer(int i):count(0),tmp_count(0) {
22 // there has a great trap when i == 0
23 if (i) {
24 while (i) {
25 digits[count++] = i % 10;
26 i /= 10;
27 }
28 } else {
29 ++count;
30 digits[0] = 0;
31 }
32 tmp_count = count;
33 }
比较函数cmp,按位从高到低循环比较,等于最大比较次数后退出;
1 bool cmp(const int& a, const int& b) {
2 Integer ia(a);
3 Integer ib(b);
4
5 int maxCmpCount = ia.getCount() + ib.getCount() - 1;
6 int curCmpCount = 0;
7
8 while (curCmpCount < maxCmpCount) {
9 int bita = ia.next();
10 int bitb = ib.next();
11
12 if (bita > bitb) {
13 return true;
14 }
15
16 if (bita < bitb) {
17 return false;
18 }
19
20 ++curCmpCount;
21 }
22
23 return false;
24 }
完整代码(Runtime:9ms)
1 #include <string>
2 #include
3 #include
4
5 class Integer {
6 public:
7 Integer(int i);
8
9 int getCount() { return count; }
10
11 int next() {
12 if (!tmp_count) {
13 tmp_count = count;
14 }
15 return digits[--tmp_count];
16 }
17
18 private:
19 int _i;
20 int count;
21 int tmp_count;
22 int digits[10];
23 };
24
25 Integer::Integer(int i):count(0),tmp_count(0) { // there has a great trap when i == 0
26 if (i) {
27 while (i) {
28 digits[count++] = i % 10;
29 i /= 10;
30 }
31 } else {
32 ++count;
33 digits[0] = 0;
34 }
35 tmp_count = count;
36 }
37
38 bool cmp(const int& a, const int& b) {
39 Integer ia(a);
40 Integer ib(b);
41
42 int maxCmpCount = ia.getCount() + ib.getCount() - 1;
43 int curCmpCount = 0;
44
45 while (curCmpCount < maxCmpCount) {
46 int bita = ia.next();
47 int bitb = ib.next();
48
49 if (bita > bitb) {
50 return true;
51 }
52
53 if (bita < bitb) {
54 return false;
55 }
56
57 ++curCmpCount;
58 }
59
60 return false;
61 }
62
63 class Solution {
64 public:
65 std::string largestNumber(std::vector<int> &num) {
66 // there is a trap when nums is all zero
67 bool allZero = true;
68 for (auto itr = num.begin(); allZero && itr != num.end(); ++itr) {
69 if (*itr != 0) {
70 allZero = false;
71 }
72 }
73
74 if (allZero) {
75 return std::string("0");
76 }
77
78 std::sort(num.begin(), num.end(), cmp);
79 std::string rel;
80 char tmp[10];
81 for (auto itr = num.begin(); itr != num.end(); ++itr) {
82 sprintf(tmp, "%d", *itr);
83 rel += tmp;
84 }
85 return rel;
86 }
87 };
View Code