上周面试了一家,出了一道算法题:
数组循环右移
将一个长度为n的数组A的元素循环右移k位, 比如
数组 1, 2, 3, 4, 5 循环右移3位之后变成 3, 4, 5, 1, 2。
只给8分钟时间。因为有点紧张第一时间脑子很乱,过了好几分钟才有思路。发现右移k位就是把后面k位挪到前面来。利用一个辅助数组来实现。后面时间不够代码也没写完,跟面试官讲了一下思路。
面试官又问如果k大于数组长度呢,我说取模,面试官说是的。面试官又问有没有不用辅助空间的做法,我没想出来。
后面查了一下是有的:先将整个数组翻转(12345变成54321),然后再将第k位前面和后面分别翻转。543变成345,21变成12。
仔细回想了一下,其实剑指offer是有类似题的,只不过剑指offer反转的是字符串。当时做的时候我也是用的第一种思路,看到剑指offer的做法的时候还不以为意,干嘛要这么麻烦,直接把后面部分接到前面不就好了?现在看来还是我太嫩了。大家做题的时候一定要掌握最优解,不要认为代码能通过就够了。
展开