LC23 合并k个有序链表
- 分治法
- 暴力k个指向k个链表头的指针找最小值O(KN) -> 维护k个元素的最小堆 O(nlgk)
最小堆自定义比较函数
struct Cmp {
bool operator() (ListNode* a, ListNode* b) {
return a->val > b->val;
}
}
注意判读p->next不为空再加入优先队列
LC 41 缺失的第一个正整数
下标置换
让n出现在nums[n-1]的位置上，0和负数忽略，注意while循环的判断一定要思考循环是否能有效终止，第二种情况如果交换的两个数相同，则while循环会变为死循环
while (nums[i] > 0 && mums[i] <= n && nums[i] != nums[nums[i] - 1]) {
swap(nums[i], nums[nums[i] - 1]);
}
// or
while (nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]])
swap(nums[i], nums[nums[i]]);
或者如果不想考虑下标和正整数元素的差1，可以先将所有元素值减1，负数不处理，但此时要注意INT_MIN不能减。
