排序多个链表
思路:
emmm… 采取上次的想法试试
一次只排序一个, 排序多次
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *result = new ListNode(0);
ListNode *backup = result;
while (true) {
int indexmin = 0;
while(indexmin < lists.size() && !lists[indexmin])
++indexmin;
ListNode *min = nullptr;
if (indexmin < lists.size())
min = lists[indexmin];
else {
if (indexmin > 0 && lists[indexmin - 1])
backup->next = lists[indexmin];
break;
}
for (int i = 1; i < lists.size(); ++i)
if (lists[i] && lists[i]->val < min->val) {
min = lists[i];
indexmin = i;
}
backup->next = min;
backup = backup->next;
lists[indexmin] = lists[indexmin]->next;
}
return result->next;
}
};
|
一次循环内只思考得到最小的一个
代码的复杂度降低了, 码字速度和debug频率也明显好多了
结果
emmmmmm…. , 这是我至今为止做的最差的一次leetcode…
难的, 想不出好方法的. 即使有想法也不做. 所以平均来说一直还算中游
不过差不多意料之中, 毕竟 hard 还是没那么容易的(除了那次用标准库偷鸡, 虽然说偷完就后悔了)
那么, 要不要看一下dalao的代码?
算了吧, 这次没怎么仔细思考算法, 刚好想尝试一下降低循环复杂度
(虽然说尝试炸了, 但还算有所收获. 在时间紧迫, 还有其他适当因素的情况下, 这种做法可以说是最有效率的)
没怎么思考就去看别人的答案, 那我还做leetcode干嘛…
但是好像又暂时想不出什么好方法, 留到以后来优化吧…