2007. 从双倍数组中还原原数组

从双倍数组中还原原数组

• 难度: medium
• 原始链接: https://leetcode.cn/problems/find-original-array-from-doubled-array
• 标签: 排序, 贪心

解法一: 排序, 贪心

go

func findOriginalArray(changed []int) []int {
  n := len(changed)
  sort.Ints(changed)
  queue := []int{}
  ans := make([]int, n>>1)
  i := 0
  for _, num := range changed {
    if len(queue) > 0 && num == queue[0] {
      queue = queue[1:]
    } else {
      if i == len(ans) {
        return []int{}
      }
      ans[i] = num
      i++
      queue = append(queue, num<<1)
    }
  }
  return ans
}