今日题目有：

  • 数组中重复的数据
  • 合并K个升序链表

1. 数组中重复的数据

题目描述

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 最多两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间（不包括存储输出所需的空间）的算法解决此问题。

示例：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]

思路

  1. 原地哈希 合理利用所有数字都在1～n这个范围，可以把每个数都当成是一个索引，我们把当前索引的值标记为负数，计作已访问。当逐个标记时遇到负数，则说明重复。
  2. 转换成位图 这里最多有100000个数，那么对于一个64位的数来说，我们需要差不多100063/64 = 1563个单元来存。每个数字都可以对应位图中的某一位。 然后遍历原数组，看对应位是否访问过即可。

Swift实现

// solution1
func findDuplicates(_ nums: [Int]) -> [Int] {
    var ans = [Int](), numsCopy = nums
    guard nums.count > 0 else { return ans }
    let len = nums.count
    for num in numsCopy {
        let curNum = abs(num)
        if numsCopy[curNum - 1] > 0 {
            numsCopy[curNum - 1] = -numsCopy[curNum - 1]
        } else {
            ans.append(curNum)
        }
    }
    return ans
}

// solution2
func findDuplicates(_ nums: [Int]) -> [Int] {
  var idxs = Array(repeating: UInt(0), count: 100063 / 64)
  // 转成位图，idxs[i] 负责 存储 i × 64 到 (i+1) × 64 - 1 这 64 个数字的状态。
  var total: [Int] = []
  for num in nums {
      let i = (num) / 64  
      let idx: UInt
      if i > 0 {
          // 移位 idx表示当前数字对应2进制数
          idx = (1 << ((num) % 64))
      } else {
          idx = (1 << ((num) % 64 - 1))
      }
      if idxs[i] & idx > 0 {
        // 对应位数是1，说明出现过，重复。
          total.append(num)
      } else {
        // 把对应位置标记成1
          idxs[i] |= idx
      }
  }
  return total
}

2. 合并K个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

思路

比较容易想到的一个方法就是分治，先两两合并，最终合成一个大的。

Swift实现

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
    if lists.count == 0 {
      return nil
    }

    if lists.count == 1 {
      return lists[0]
    }
  
    let mid = lists.count/2
  
    let left = mergeKLists(Array(lists[0..<mid]))
    let right = mergeKLists(Array(lists[mid..<lists.count]))
  
    return mergeTwoLists(left, right)
}

func mergeTwoLists(_ first: ListNode?, _ second: ListNode?) -> ListNode? {
    var firstNode = first, secondNode = second
    let head = ListNode.init(-1)
    var current:ListNode? = head
    while firstNode != nil && secondNode != nil{
        if firstNode?.val ?? 0 < secondNode?.val ?? 0{
            current?.next = firstNode
            firstNode = firstNode?.next
            current = current?.next
        } else {
            current?.next = secondNode
            secondNode = secondNode?.next
            current = current?.next
        }
    }
    if firstNode != nil {
        current?.next = firstNode
    } else if secondNode != nil {
        current?.next = secondNode
    }
    return head.next
}