教3妹学编程： 29. 乐团站位

2哥：oh baby 情话多说一点 爱我就多看一眼。表现多一点点　让我能　真的看见。

2哥正在很陶醉的哼着甜心姐姐王心凌的歌曲。

3妹：2哥呀，你也喜欢甜心教主的歌曲啊，没想到你也是个王心凌男孩，中老年团粉啊。

2哥：我当然是啊，甜心姐姐唱歌多好听， 声音多甜啊。

3妹：先别唱了，2哥，今天遇到了一个题目，想了好久也没做出来，你帮我看看。

2哥：原来是有求于我，让我来see see。

某乐团的演出场地可视作 num * num 的二维矩阵 grid（左上角坐标为 [0,0])，每个位置站有一位成员。乐团共有 9 种乐器，乐器编号为 1~9，每位成员持有 1 个乐器。

为保证声乐混合效果，成员站位规则为：自 grid 左上角开始顺时针螺旋形向内循环以 1，2，…，9 循环重复排列。例如当 num = 5 时，站位如图所示

请返回位于场地坐标 [Xpos,Ypos] 的成员所持乐器编号。

示例 1：

输入：num = 3, Xpos = 0, Ypos = 2

输出：3

解释：

示例 2：

输入：num = 4, Xpos = 1, Ypos = 2

输出：5

解释：

提示：

1 <= num <= 10^9
0 <= Xpos, Ypos < num

2哥：这题有什么难的，按照题目要求，模拟顺时针螺旋形向内循环的过程不就可以了嘛，我直接可以写代码。

public int orchestraLayout(int num, int xPos, int yPos) {
int i = 0, j = 0, direction = 6, len = 1;
		int left = 0, top = 1, right = num - 1, bottom = num - 1;
		while (i != xPos || j != yPos) {
			switch (direction) {
			case 6:
				if (j != right)j++;
				else {
					i++;
					direction = 2;
					right--;
				}
				break;
			case 2:
				if (i != bottom)i++;
				else {
					j--;
					direction = 4;
					bottom--;
				}
				break;
			case 4:
				if (j != left)j--;
				else {
					i--;
					direction = 8;
					left++;
				}
				break;
			case 8:
				if (i != top)i--;
				else {
					j++;
					direction = 6;
					top++;
				}
				break;
			}
			len++;
		}
		return (len - 1) % 9 + 1;

    }

3妹： 这种暴力求解我也想到了，可是时间复杂度是o(n^2), 超时时间限制了，有好的方法吗？

2哥：还可以这样来解，我们一层一层的“剥开”矩阵，即浪费时间又浪费空间，我们能不能一次性“剥开”多层矩阵呢？
设num==n，矩阵最外面“一层”可以站f(n)个人

class Solution {
       public int orchestraLayout(int n, int xPos, int yPos) {
        //一共几圈
        int quan=(n+1)/2;
        long num=n;
        //第几圈
        int layer = Math.min(Math.min(yPos,xPos),Math.min( n - xPos - 1, n - yPos - 1))+1;
        //总面积
        long area=num*num;
        //当前所在圈面积
        long zhong=(num-2*(layer-1));
        zhong*=zhong;
        //求差 +1 得到当前圈左上角编号
        long index=(area-zhong)%9+1;
        //右边界
        int right=n-layer;
        //左边界
        int left=layer-1;
        if(xPos==left){
            //在 --- 上
            index+=yPos-left;
        }else if(yPos==right){
            //在   |上
            index+=right-left;
            index+=xPos-left;
        }else if(xPos==right){
            //在 __ 上
            index+=2*(right-left);
            index+=right-yPos;
        }else{
            //在 |  上
            index+=3*(right-left);
            index+=right-xPos;
        }
        return (int)(index%9==0?9:index%9);
    }
}

3妹：呀，这样复杂度只有o(1), 可以了呢。 还是2哥牛。