Code Signal – 相似数组(Are Similar)

Two arrays are called similar if one can be obtained from another by swapping at most one pair of elements in one of the arrays.

Given two arrays a and b, check whether they are similar.

Example:

For a = [1, 2, 3] and b = [1, 2, 3], the output should be areSimilar(a, b) = true.

The arrays are equal, no need to swap any elements.

For a = [1, 2, 3] and b = [2, 1, 3], the output should be areSimilar(a, b) = true.

We can obtain b from a by swapping 2 and 1 in b.

For a = [1, 2, 2] and b = [2, 1, 1], the output should be areSimilar(a, b) = false.

Any swap of any two elements either in a or in b won’t make a and b equal.

Input/Output:

[execution time limit] 4 seconds (js)

[input] array.integer a

Array of integers.

Guaranteed constraints:

3 ≤ a.length ≤ 105,

1 ≤ a[i] ≤ 1000.

[input] array.integer b

Array of integers of the same length as a.

Guaranteed constraints:

b.length = a.length,

1 ≤ b[i] ≤ 1000.

[output] boolean

true if a and b are similar, false otherwise.

解题思路
解题思路和 近乎增长序列(almostIncreasingSequence) 很相似，不过有点稍微变种。

因为先决条件最多只能调换 一个数组中 的 一对元素，所以二者之间的不同只能为 0(不需要调换)，或者 2(调换一对)

当最大不同为 0 时，代表数组完全相等，返回 true 即可

当最大不同为 2 时，因为只需要交换一个数组中的两个元素，所以只要满足下列条件即可：

a [ y ] = b [ x ] , a [ x ] = b [ y ] a[y] = b[x], a[x] = b[y]a[y]=b[x],a[x]=b[y]

这样跑下来的时间复杂度是 O ( n ) O(n)O(n)，需要遍历一次所有的数组，空间复杂度为 O ( n ) O(n)O(n)，需要保存所有不同数。当然，后者也可以被优化到 O ( 1 ) O(1)O(1)，只需要当 包含所有不同的数组 长度超过 2 时直接返回即可，这样最大也就需要 3 个额外空间去进行存储。