java - 左循环旋转一个 ArrayList 然后获取最大元素的索引

Question

我需要根据第二个数组列表的每个元素左循环旋转一个数组列表，然后返回另一个具有旋转数组列表的最大元素索引的列表。 (每次旋转都要在原来的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() 更好？

Answer 1

首先，忘掉实际旋转的任何东西，而是考虑其中一个元素(最大的元素)会发生什么情况。

我不想用勺子喂你代码。相反，请考虑以下想法:

找到最大元素的索引，称之为iMax。

旋转n后最大元素的位置是(iMax - n + array.length) % array.length。

如果 n 可以小于零或大于 array.length，您需要使用以下事实将其置于该范围内:对于正 n，旋转n 和 n % array.length 给出相同的结果。

您应该能够围绕这些想法构建一些代码。