面试题：Java中ArrayList查找算法的优化

Question

在Java的ArrayList中，假设你要频繁查找某个元素，默认的查找方式效率可能不高。请描述一种优化查找的思路，并编写代码实现（可借助相关数据结构辅助）。

Answer 1

1. 优化思路：
   • 由于ArrayList默认查找是通过遍历实现，时间复杂度为$O(n)$。为了优化查找，可以借助HashMap。HashMap的containsKey方法时间复杂度为$O(1)$（平均情况）。我们可以在向ArrayList添加元素的同时，将元素作为key，其在ArrayList中的索引作为value存储到HashMap中。这样在查找元素时，先通过HashMap快速判断元素是否存在，如果存在则可通过HashMap获取其索引，避免在ArrayList中进行线性查找。
2. 代码实现：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class OptimizedArrayList<T> {
    private ArrayList<T> list;
    private Map<T, Integer> map;

    public OptimizedArrayList() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }

    public void add(T element) {
        list.add(element);
        map.put(element, list.size() - 1);
    }

    public boolean contains(T element) {
        return map.containsKey(element);
    }

    public int indexOf(T element) {
        return map.getOrDefault(element, -1);
    }
}

你可以使用以下方式测试这个类：

public class Main {
    public static void main(String[] args) {
        OptimizedArrayList<Integer> optimizedList = new OptimizedArrayList<>();
        optimizedList.add(10);
        optimizedList.add(20);
        optimizedList.add(30);

        System.out.println("是否包含20: " + optimizedList.contains(20));
        System.out.println("20的索引: " + optimizedList.indexOf(20));
    }
}