我有一个面试问题。
编写包含以下方法的类UnlimitedArrayInt。每种方法的复杂度应为O [1]：
* void setall(int number) –所有整数均设置为给定数字；
* int get(int index) –返回给定索引处的数字。索引可以是任何正整数值；
* void set(int index,int number)-在给定索引处设置数字。数组不受限制，因此可以是任何正整数值； number可以是任何整数值。
正如他们告诉我的解决方案不基于常规数组。
因此，谁能向我解释哪种数据结构更适合使用，以及如何使用复杂度O（1）来实现setall方法，因为在我看来，它总是复杂度O（n）导致我们需要遍历所有索引以设置新值任何数据结构的所有元素。
如何在一项操作中同时为数据结构的所有元素设置一个值
•
问答
show1234ab 回答：如何在一项操作中同时为数据结构的所有元素设置一个值
您需要使用Map以及将在集合中使用的一个公共值。如果用户设置该值，则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);
}
}