• 拿到题的直觉解法
  • 为什么题目给你的nums1已经有足够的长度了？
  • 因为在merge sorted的时候，必须有一个辅助的array，来帮助合并，否则的话，就很难(也许有办法)做到无需额外空间也能sort了。 比如[4,5,6,7,1,2,3,4]，由前半部分和后半部分组成，分别是一个sorted array；如果不需要额外空间，怎么直接排序？
  • 这里我们要一个额外的空间，然后双指针从尾部和中部，边比较边从尾部填入temp array，然后复制到原array。从头部也可以；
  • 所以这里我们总结的经验是，对于这种merge sorted问题，不要浪费时间想办法在线合并，而应该借助额外的空间来合并。
  • 这一题不需要额外的空间了，因为nums1本身就扮演了额外空间的角色；(所以如果我们发现不允许额外空间，那肯定题目偷偷给了额外的空间，来规避这种缺陷)
  • 这题从尾部扫，nums1就可以当作temp array使用。

AC

time: space: