Co2y's Blog

spiral matrix中任意位置的元素

发表于 | 分类于 |

今天面试的一道题，回来的路上想出来了。。结果当然是杯具了。。

题目

给一个回形矩阵，例如

1
2
3
123
894
765

问任意(i, j)位置的元素是多少

解法

假设是一个M*N的矩阵，既然是回形的，对于所求位置(i, j)，我们可以判断它所处于第几个环，即

1
min(i, j, M - i - 1, N - j - 1)

而第k环，所包含的元素个数为(k从1计)

1
2*(M + N - 2) - 8*(k - 1)

所以前n环的元素个数为(n从0计)

1
2
3
sum(0 <= i < n : 2*(M + N - 2) - 8*i) = 2*n*(M + N - 2) - 8 * sum(0 <= i < n : i)
                                      = 2*n*(M + N - 2) - 8 * n * (n - 1) / 2
                                      = 2*n*(M + N - 2*n)

最终结果 （copy from stackoverflow）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
if (n == y) {
    // top of this round
    index += x - n;
} else {
    // add full top of this round
    index += M - 2 * n;
    if (n == M - x - 1) {
        // right side of this round
        index += y - (n + 1);
    } else {
        // add full right side  of this round
        index += N - 2 * n - 1;
        if (n == N - y - 1) {
            // bottom of this round
            index += N - x - 1 - (n + 1);
        } else {
            // add full bottom of this round
            index += M - 2 * n - 1;
            // left side of this round
            index += M - y - 1 - (n+1);
        }
    }
}

小结

好好学基础（语言+算法），然后深入一个领域。至于碰上文不对题的面试官，那就是运气玄学了。