LeetCode.合并两个有序数组

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。格雷编码序列必须以0开头。

• 示例 1:
  输入: 2
  输出: [0,1,3,2]
  解释:
  00 - 0
  01 - 1
  11 - 3
  10 - 2
  对于给定的 n，其格雷编码序列并不唯一。
  例如，[0,2,3,1] 也是一个有效的格雷编码序列。
  00 - 0
  10 - 2
  11 - 3
  01 - 1
• 示例 2:
  输入: 0
  输出: [0]
  解释: 我们定义格雷编码序列必须以 0 开头。

解法：

object GrayCode {
     def main(args: Array[String]): Unit = {
          println(grayCode(1))
          println(grayCode(2))
          println(grayCode(3))
          println(grayCode(4))
     }

     /**
      * 在n-1的序列前面补0或1，先正序补0，再返序补1
      * 00 01 11 10
      * 000 001 011 010 110 111 101 100
      */
     def grayCode(n: Int): List[Int] = {
          if(n == 0) return List()
          val arr = new Array[Int](Math.pow(2, n).toInt)
          arr(0) = 0
          arr(1) = 1

          for (i <- 2 to n) {
               for (j <- Math.pow(2, i - 1).toInt until Math.pow(2, i).toInt) {
                    val last = arr(Math.pow(2, i).toInt - j - 1)
                    val plus = (1 << i - 1)
                    arr(j) = last + plus
               }
          }

          arr.toList
     }
}