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

Question

我需要根据第二个数组列表的每个元素左循环旋转一个数组列表，然后 return 另一个具有旋转数组列表的最大元素索引的列表。（每次旋转都要在原来的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 时，总是显示 "Terminated due to timeout" 错误，因为我运行在 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

如果您需要 return 每次旋转后仅需要最大元素的索引，那么您不需要实际旋转列表。您可以计算初始列表中最大元素的索引，然后使用一些数学计算现有索引将在旋转后转换为哪个索引。

Answer 2

我尝试了您发布的代码片段，您可以从上面的代码中查看：

package Whosebug;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class Rotate {

    public static void main(String[] args) {

        int[] a = { 1, 2, 3, 4};  
        List<Integer> rotatelist = Arrays.stream(a).boxed().collect(Collectors.toList());
        int[] b = { 1, 2, 3};  
        List<Integer> rotate = Arrays.stream(b).boxed().collect(Collectors.toList());
        List<Integer> maxindexes = maxIndexes(rotate, rotatelist);
        System.out.println(maxindexes);
    }

    public static List<Integer> maxIndexes(List<Integer> rotate, List<Integer> rotatelist) {
        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));

        //added to print rotated arrays
        System.out.println(rotatelist);

        //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;
    }

}

你可以查看我在打印旋转数组的方法中使用了指令System.out.println(rotatelist)，我得到了以下结果：

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,1,2,3] : 最大元素索引= 0 所以第三个数组是 [4, 1, 2, 3] （原始数组旋转了三个位置）而不是 [4, 3, 2, 1].

您提到的超时问题的可能解决方案是复制原始数组： [1, 2, 3, 4] 现在是 [1, 2, 3, 4, 1, 2, 3, 4]。现在您可以获得数组 [1, 2, 3, 4] 的旋转，迭代新的重复数组：

for rotate[0] = 1 旋转数组从重复数组的索引 1 开始 [1, 2, 3, 4, 1, 2, 3, 4] and index = 1 and length = 4 -> [2, 3, 4, 1]

for rotate[1] = 2 旋转数组从重复数组的索引 2 开始 [1, 2, 3, 4, 1, 2, 3, 4] and index = 2 and length = 4 -> [3, 4, 1, 2]

for rotate[2] = 3 旋转数组从重复数组的索引 2 开始 [1, 2, 3, 4, 1, 2, 3, 4] and index = 3 and length = 4 -> [4, 1, 2, 3]

Answer 3

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

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

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

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

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

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

Answer 4

也许你可以试试这个解决方案

public static List<Integer> rotateLeft(int d, List<Integer> arr) {
// Get head of the rotated array
int head = -99;
    for(int i = 0; d >=0; i++){
        head = arr.get(i);
        if(i == arr.size()-1){
            i = -1;
        }   
        d--;   
    }
    // get elements from head to the end of the original array
    List<Integer>sub = arr.subList(arr.lastIndexOf(head),arr.size());

    // get elements from begginning to head
    List<Integer>remainder = arr.subList(0,arr.lastIndexOf(head));

    // concat them 
    List<Integer>newl = new ArrayList<Integer>(sub);
    newl.addAll(remainder);

    return newl;
}

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

Left circular rotate an ArrayList then get index of max element

java

arraylist

circular-buffer