如何在一个操作中（同时）为数据结构的所有元素设置一个值

Question

我有一个面试问题。写入包含以下方法的类UnlimitedArrayInt。每种方法的复杂性应为O[1]：void setAll（int number）–所有整数都设置为给定的数字；*int get（int index）–返回给定索引处的数字。索引可以是任何正整数值；*voidset（int index，int number）在给定索引处设置编号。数组不受限制，所以它可以是任何正整数值；数字可以是任何整数值。正如他们告诉我的那个样，这个解决方案不是基于正则数组的。那么，有谁能解释一下什么样的数据结构更适合使用，以及如何实现复杂度为O（1）的setAll方法，因为我认为它总是复杂度为O（n），因为我们需要迭代所有索引来设置任何数据结构的所有元素的新值。

Answer 1

您需要使用Map和一个您将在set中使用的公共值。如果用户设置值，Map将充当覆盖。

以下内容：

public class UnlimitedArrayInt {
    Map<Integer, Integer> values;
    int commonValue;//default value to return if not found

    public UnlimitedArrayInt() {
        values = new HashMap<>();
        commonValue = -1;
    }

    /**
        use common value that you are going to use and at the same time reset all the instance of map (GC would clear all the reference at the back and this is a trade off of clear vs new instance that am making). Runs in O(1) time.
    */
    public void setAll(int number) {
        commonValue = number;
        values = new HashMap<>();
    }
    /**
        return if value was set else return the common value across your data structure if any was used. Else return -1. Runs in O(1) time.
     */
    public int get(int index) {
         return values.getOrDefault(index, commonValue);
    }

    /**
        Override the existing common value which would take the priority over common value. Runs in O(1) time.
    */
    public set(int index, int number) {
         return values.put(index, number);
    }
}