• 【Java刷题】初始化List应该选择ArrayList还是LinkedList

    文章目录

    前言

    记录java刷题的一个大坑，ArrayList和LinkedList效率差别

    题目

    6235. 逐层排序二叉树所需的最少操作数目

    解题思路

    层次遍历，对每一层，按照排序的结果对数组进行交换，记录交换次数即可。

    遇到的坑：ArrayList和LinkedList

    这是第319场周赛T3，这题被卡了好久，看了题解以后发现和我的思路一样，但我的代码就是有两个测试用例超时。

    经过反复提交测试，发现是初始化List时用ArrayList和LinkedList的区别。

    未通过代码

    class Solution {
    public int minimumOperations(TreeNode root) {
        //层次遍历结果
        List<List<Integer>> list = levelOrder(root);
        
        int res = 0;
        //加上每层按照排序结果交换的次数
        for(int i = 0; i < list.size(); i++){
            res += getMinswap(list.get(i));
        }

        return res;
    }

    List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tmp = new LinkedList<>();
            for(int i = 0; i < size; i++){
                TreeNode now = queue.poll();
                tmp.add(now.val);
                if(now.left != null) queue.offer(now.left);
                if(now.right != null) queue.offer(now.right);
            }
            list.add(tmp);
        }
        return list;
    }

    int getMinswap(List<Integer> nums){
        if(nums.size() == 1) return 0;
        int n = nums.size();
        int res = 0;
        List<Integer> sortedNums = new LinkedList<>(nums);
        Collections.sort(sortedNums);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < sortedNums.size(); i++){
            map.put(sortedNums.get(i), i);
        }
        for(int i = 0; i < n; ){
            if(sortedNums.get(i).equals(nums.get(i))){
                i++;
                continue;
            }
            Collections.swap(nums, i, map.get(nums.get(i)));
            res++;
        }

        return res;
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    通过代码

    class Solution {
    public int minimumOperations(TreeNode root) {
        //层次遍历结果
        List<List<Integer>> list = levelOrder(root);
        
        int res = 0;
        //加上每层按照排序结果交换的次数
        for(int i = 0; i < list.size(); i++){
            res += getMinswap(list.get(i));
        }

        return res;
    }

    List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode now = queue.poll();
                tmp.add(now.val);
                if(now.left != null) queue.offer(now.left);
                if(now.right != null) queue.offer(now.right);
            }
            list.add(tmp);
        }
        return list;
    }

    int getMinswap(List<Integer> nums){
        if(nums.size() == 1) return 0;
        int n = nums.size();
        int res = 0;
        List<Integer> sortedNums = new ArrayList<>(nums);
        Collections.sort(sortedNums);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < sortedNums.size(); i++){
            map.put(sortedNums.get(i), i);
        }
        for(int i = 0; i < n; ){
            if(sortedNums.get(i).equals(nums.get(i))){
                i++;
                continue;
            }
            Collections.swap(nums, i, map.get(nums.get(i)));
            res++;
        }

        return res;
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    小结

    把我原来的LinkedList改成ArrayList就过了。

    ArrayList和LinkedList的区别

    ArrayList和LinkedList有什么区别：

    1. ArrayList底层结构是顺序表(基于数组)；
      LinkList是链表;
    2. ArrayList数据存放在内存空间上;
      LinkList不是存放在连续的内存空间上;
    3. ArrayList能够高效的进行“随机访问” ,时间复杂度是O(1);
    4. LinkList能够高效的进行插入删除，时间复杂度为O(1)。

    在刷题的时候应该如何选择

    大部分应该选择ArrayList，因为很多时候我们都要遍历数组，此时就要调用get方法访问元素，对于随机访问，ArrayList比LinkedList快。

    由于LinkList能够高效的进行插入删除，在任意位置插入操作对应add(int index, E element)，删除操作对应remove(int index)，所以遇到这两种操作比较多的时候应该用LinkList。这种情况在我刷题的过程中遇到得比较少。

    排序效率

    Collections.sort()内部是归并排序，下面对ArrayList和LinkedList实现的List做一个简单的排序效率测试。

    测试代码

    import java.util.*;

public class Main {
    public static void main(String[] args) {
        int count = 10000000;

        List<Integer> listArray = new ArrayList<>();
        List<Integer> listLinked = new LinkedList<>();
        Random random = new Random();
        //生成count个随机值
        for (int i = 0; i < count; i++) {
            int rand = random.nextInt();
            listArray.add(rand);
            listLinked.add(rand);
        }

        //开始计时
        long startTime1 = System.currentTimeMillis();
        //对ArrayList排序
        Collections.sort(listArray);
        long endTime1 = System.currentTimeMillis();
        long usedTime1 = (endTime1 - startTime1);

        //开始计时
        long startTime2 = System.currentTimeMillis();
        //对LinkedList排序
        Collections.sort(listLinked);
        long endTime2 = System.currentTimeMillis();
        long usedTime2 = (endTime2 - startTime2);

        //打印排序时间
        System.out.println("ArrayList排序用时：" + usedTime1);
        System.out.println("LinkedList排序用时：" + usedTime2);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    测试结果

    在这里插入图片描述

    单从排序效率来看LinkList是比ArrayList高的，然而根据我上面那道题的例子，里面也有用到排序，当我把排序的那个List改为LinkList时仍然无法通过，应该是排完序之后又对数组进行了遍历，而遍历ArrayList是快的。

    遍历效率

    测试代码

    import java.util.*;

public class Main {
    public static void main(String[] args) {
        int count = 100000;

        List<Integer> listArray = new ArrayList<>();
        List<Integer> listLinked = new LinkedList<>();
        Random random = new Random();
        //生成count个随机值
        for (int i = 0; i < count; i++) {
            int rand = random.nextInt();
            listArray.add(rand);
            listLinked.add(rand);
        }

        //开始计时
        long startTime1 = System.currentTimeMillis();
        //对ArrayList遍历
        for(int i = 0; i < listArray.size(); i++){
            int a = listArray.get(i);
        }
        long endTime1 = System.currentTimeMillis();
        long usedTime1 = (endTime1 - startTime1);

        //开始计时
        long startTime2 = System.currentTimeMillis();
        //对LinkedList遍历
        for(int i = 0; i < listLinked.size(); i++){
            int a = listLinked.get(i);
        }
        long endTime2 = System.currentTimeMillis();
        long usedTime2 = (endTime2 - startTime2);

        //打印遍历时间
        System.out.println("ArrayList遍历用时：" + usedTime1);
        System.out.println("LinkedList遍历用时：" + usedTime2);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    测试结果

    在这里插入图片描述
    由此可见，ArrayList的遍历效率比LinkList高，而且超出LinkList的部分大于LinkList排序超出ArrayList的部分。因此在排序和遍历操作都存在的情况，还是应该选择ArrayList。

    结论

    刷题的时候首选ArrayList。遇到add(int index, E element)和remove(int index)操作频繁的时候，再改用LinkList。

  • 相关阅读:
    分库分表ShardingJDBC最佳实践
    Web前端：创建符合Web可访问性标准的HTML布局
    PCB入门介绍与电阻电容电感类元件的创建
    彻底搞懂blob对象，实现文件下载，文件分片技术
    Collections工具类
    FreeRTOS简单内核实现5 阻塞延时
    剑指 Offer 53 - I. 在排序数组中查找数字 I（改进二分）
    CTFHub技能树 Web-文件上传详解
    mysql之GROUP_CONCAT
    Redis延迟双删-架构案例2021（三十二）
  • 原文地址：https://blog.csdn.net/m0_46283220/article/details/127833553