arr[i] + arr[k] != 2*arr[j]

一、题目描述：

给定一个正整数M，请构造出一个长度为M的数组arr， 要求对于任意的i,j,k三个位置，如果i<j<k,都有arr[i] + arr[k] != 2*arr[j]，返回构造出的arr(满足情况的一种)。

示例：

示例 1：

输入：1

输出：[1]

示例 2：

输入：3

输出：[1, 5, 2]

示例 3：

输入：5

输出：[ 1, 5, 3, 2, 6]

二、思路分析：

利用奇数偶数来举例。此题核心主要是列举一个满足 a + c != 2b的例子。

当长度为1时，直接返回任意一个数都满足情况。

当长度不为1时，我们可以将数组划分成两半，前半份为奇数，后半份为偶数。

长度为2时，arr = [1,2]。根据长度为1的扩展。分别为第一个奇数、第一个偶数。

长度为3时，arr = [1,3,2]。根据长度为2（3的一半）的扩展。第一个奇数、第二个奇数，第一个偶数。

长度为4时，arr = [1,3,2,4]。根据长度为2（4的一半）的扩展。第一个奇数、第二个奇数，第一个偶数、第二个偶数。

长度为5时，arr = [1, 5, 3, 2, 6]。根据长度为3（5的一半）的扩展。第一个奇数、第三个奇数、第二个奇数，第一个偶数、第三个偶数。

。。。

以此类推。

使用递归，利用上一个结果，求其结果。

三、AC 代码：

function makeNo(size) {
  if (size === 1) return [1]
  let halfSize = Math.floor((size + 1) / 2)
  console.log(halfSize);
  let base = makeNo(halfSize)
  let res = []
  let index = 0
  for (; index < halfSize; index++) {
    res[index] = base[index] * 2 - 1
  }
  console.log(res,index)
  for (let i = 0; index < size; index++, i++) {
    // 偶数
    res[index] = base[i] * 2
    console.log(base[i])
  }
  return res
}

四、总结：

此题只要满足情况即可，根据奇数偶数只是其中一种方法。

作者：ClyingDeng

链接：https://juejin.cn/post/6952773184533823496

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。