我需要根据第二个数组列表的每个元素左循环旋转一个数组列表,然后返回另一个具有旋转数组列表的最大元素索引的列表。 (每次旋转都要在原来的arraylist编队上进行)
例如我有这两个数组列表:rotatelist[1,2,3,4],rotate[1,2,3]
流程是:
rotatelist[1,2,3,4],rotate[1] -> [2,3,4,1] : 最大元素索引= 2
rotatelist[1,2,3,4],rotate[2] -> [3,4,1,2] : 最大元素索引= 1
rotatelist[1,2,3,4],rotate[3] -> [4,3,2,1] : 最大元素索引= 0
下面的代码工作正常,但是当一个测试用例的两个数组列表元素大小达到大约 100,000 时,“由于超时而终止”错误总是显示,因为我在 HackerRank 上运行它
List<Integer> indices = new ArrayList<>(rotate.size());
for(int i=0;i<rotate.size();i++){
//rotate arraylist to the left
Collections.rotate(rotatelist,-rotate.get(i));
//get and insert max element index to array
indices.add(rotatelist.indexOf(Collections.max(rotatelist)));
//rotate back to previous positions
Collections.rotate(rotatelist,rotate.get(i));
}
return indices;
那么有没有其他方法可以优化这段代码的性能呢?
在性能方面使用传统的 for 循环是否比使用 Collections.rotate() 更好?
最佳答案
首先,忘掉实际旋转的任何东西,而是考虑其中一个元素(最大的元素)会发生什么情况。
我不想用勺子喂你代码。相反,请考虑以下想法:
找到最大元素的索引,称之为iMax
。
旋转n
后最大元素的位置是(iMax - n + array.length) % array.length
。
如果 n
可以小于零或大于 array.length
,您需要使用以下事实将其置于该范围内:对于正 n,旋转n
和 n % array.length
给出相同的结果。
您应该能够围绕这些想法构建一些代码。
关于java - 左循环旋转一个 ArrayList 然后获取最大元素的索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57628994/