rust 解法, 执行用时: 91 ms, 内存消耗: 27.9 MB, 提交时间: 2024-04-26 07:38:46

struct SnapshotArray {
    snap_cnt: i32,
    data: Vec<Vec<(i32, i32)>>,
}

impl SnapshotArray {
    fn new(length: i32) -> Self {
        SnapshotArray {
            snap_cnt: 0,
            data: vec![vec![]; length as usize],
        }
    }
    
    fn set(&mut self, index: i32, val: i32) {
        self.data[index as usize].push((self.snap_cnt, val));
    }
    
    fn snap(&mut self) -> i32 {
        let ans = self.snap_cnt;
        self.snap_cnt += 1;
        ans
    }
    
    fn get(&self, index: i32, snap_id: i32) -> i32 {
        let idx = self.binary_search(index, snap_id);
        if idx == 0 {
            return 0;
        }
        self.data[index as usize][idx - 1].1
    }

    fn binary_search(&self, index: i32, snap_id: i32) -> usize {
        let mut low = 0;
        let mut high = self.data[index as usize].len();
        while low < high {
            let mid = low + ((high - low) / 2);
            let (x, y) = self.data[index as usize][mid];
            if x > snap_id + 1 || (x == snap_id + 1 && y >= 0) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        low
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * let obj = SnapshotArray::new(length);
 * obj.set(index, val);
 * let ret_2: i32 = obj.snap();
 * let ret_3: i32 = obj.get(index, snap_id);
 */

javascript 解法, 执行用时: 576 ms, 内存消耗: 85.4 MB, 提交时间: 2024-04-26 07:38:22

var SnapshotArray = function(length) {
    this.snap_cnt = 0;
    this.data = Array.from({length}, () => []);
};

SnapshotArray.prototype.set = function(index, val) {
    this.data[index].push([this.snap_cnt, val]);
};

SnapshotArray.prototype.snap = function() {
    return this.snap_cnt++;
};

SnapshotArray.prototype.get = function(index, snap_id) {
    const idx = binarySearch(index, snap_id, this.data);
    if (idx === 0) {
        return 0;
    }
    return this.data[index][idx - 1][1];
};

const binarySearch = (index, snap_id, data) => {
    let low = 0, high = data[index].length;
    while (low < high) {
        const mid = low + Math.floor((high - low) / 2);
        const [x, y] = data[index][mid];
        if (x > snap_id + 1 || (x == snap_id + 1 && y >= 0)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * var obj = new SnapshotArray(length)
 * obj.set(index,val)
 * var param_2 = obj.snap()
 * var param_3 = obj.get(index,snap_id)
 */

cpp 解法, 执行用时: 335 ms, 内存消耗: 169.1 MB, 提交时间: 2024-04-26 07:37:31

class SnapshotArray {
public:
    SnapshotArray(int length): snap_cnt(0), data(length) {}
    
    void set(int index, int val) {
        data[index].emplace_back(snap_cnt, val);
    }
    
    int snap() {
        return snap_cnt++;
    }
    
    int get(int index, int snap_id) {
        auto x = upper_bound(data[index].begin(), data[index].end(), pair{snap_id + 1, -1});
        return x == data[index].begin() ? 0 : prev(x)->second;
    }

private:
    int snap_cnt;
    vector<vector<pair<int, int>>> data;
};


/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

php 解法, 执行用时: 1584 ms, 内存消耗: 66.2 MB, 提交时间: 2023-09-08 16:04:19

class SnapshotArray {
    /**
     * @param Integer $length
     */
    function __construct($length) {
        $this->snap = array_fill(0, $length, [0 => 0]);
        $this->id = 0;
    }
    
    /**
     * @param Integer $index
     * @param Integer $val
     * @return NULL
     */
    function set($index, $val) {
        $this->snap[$index][$this->id] = $val;
    }
    
    /**
     * @return Integer
     */
    function snap() {
        $this->id++;
        return $this->id - 1;
    }
  
    /**
     * @param Integer $index
     * @param Integer $snap_id
     * @return Integer
     */
    function get($index, $snap_id) {
        # 选择要查找的元素的字典
        $d = $this->snap[$index];
        # 如果快照恰好存在, 直接返回
        $keys = array_keys($d);
        if ( in_array($snap_id, $keys, true) )
            return $d[$snap_id];
        # 不存在则进行二分搜索, 查找快照前最后一次修改
        $i = $this->binary_search($keys, $snap_id);
        return $d[$keys[$i - 1]];
    }
    
    function binary_search($array, $value) {
        $left = 0;
        $right = count($array);

        while ($left < $right) {
            $mid = intval(($left + $right) / 2 );
            if ($array[$mid] < $value) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        return $left;
    }
}


/**
 * Your SnapshotArray object will be instantiated and called as such:
 * $obj = SnapshotArray($length);
 * $obj->set($index, $val);
 * $ret_2 = $obj->snap();
 * $ret_3 = $obj->get($index, $snap_id);
 */

java 解法, 执行用时: 44 ms, 内存消耗: 81.8 MB, 提交时间: 2023-09-08 14:57:36

class SnapshotArray {
    int id = 0;
    List<int[]>[] snapshots;

    public SnapshotArray(int length) {
        snapshots = new List[length];
        for (int i = 0; i < length; i++) {
            snapshots[i] = new ArrayList<int[]>();
        }
    }

    public void set(int index, int val) {
        snapshots[index].add(new int[]{id, val});
    }

    public int snap() {
        int curr = id;
        id++;
        return curr;
    }

    public int get(int index, int snap_id) {
        List<int[]> snaplist = snapshots[index];
        int low = -1, high = snaplist.size() - 1;
        while (low < high) {
            int mid = low + (high - low + 1) / 2;
            if (snaplist.get(mid)[0] <= snap_id) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low >= 0 ? snaplist.get(low)[1] : 0;
    }
}


/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */

golang 解法, 执行用时: 432 ms, 内存消耗: 31.5 MB, 提交时间: 2023-09-08 14:56:48

type SnapshotArray struct {
    Id int
    Ids [][]int
    Arr [][]int
}

func Constructor(l int) SnapshotArray {
    var ids, arr [][]int
    for i:=0; i<l; i++ {
        ids = append(ids, []int{0})
        arr = append(arr, []int{0})
    }
    return SnapshotArray{0, ids, arr}
}

func (p *SnapshotArray) Set(index int, val int)  {
    var n = len(p.Ids[index])
    if p.Id > p.Ids[index][n-1] {
        p.Ids[index] = append(p.Ids[index], p.Id)
        p.Arr[index] = append(p.Arr[index], val)
    } else {
        p.Arr[index][n-1] = val
    }
}

func (p *SnapshotArray) Snap() int {
    var ret = p.Id
    p.Id++
    return ret
}

func (p *SnapshotArray) Get(index int, snap_id int) int {
    return p.Arr[index][sort.SearchInts(p.Ids[index], snap_id+1)-1]
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * obj := Constructor(length);
 * obj.Set(index,val);
 * param_2 := obj.Snap();
 * param_3 := obj.Get(index,snap_id);
 */

golang 解法, 执行用时: 396 ms, 内存消耗: 31.3 MB, 提交时间: 2023-09-08 14:40:37

type SnapshotArray struct {
	id   int
	snap map[int]map[int]int
}


func Constructor(length int) SnapshotArray {
	return SnapshotArray{0, make(map[int]map[int]int, 0)}
}

func (this *SnapshotArray) Set(index int, val int) {
	if this.snap[index] == nil {
		this.snap[index] = make(map[int]int, 0)
	}
	//记录下一次快照前，改变过的index值
	this.snap[index][this.id] = val
}

func (this *SnapshotArray) Snap() int {
	this.id++
	//返回上一次的snap_id
	return this.id - 1
}

/*如果index当前snap_id不存在，则说明snap_id这次快照跟snap_id-1这次快照之间index的值没变化过
二分找到snpa_id前第一个存在的快照id
但是go没有unorderedmap，还要枚举allkeys排序再二分,还不如直接遍历O(N)
*/
func (this *SnapshotArray) Get(index int, snap_id int) int {
	if value, ok := this.snap[index][snap_id]; ok {
		return value
	}
	//枚举所有key
	allkeys := make([]int, len(this.snap[index]))
	i := 0
	for key, _ := range this.snap[index] {
		allkeys[i] = key
		i++
	}
	//排序以备二分
	sort.Ints(allkeys)

	low := 0
	high := len(allkeys) - 1
	for low <= high {
		mid := (low + high) / 2
		if allkeys[mid] < snap_id {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	//如果low==0，说明不存在这样的快照，返回初始值0
	if low == 0 {
		return 0
	} else {
		//找到第一个比目标值大的下标，需要-1
		return this.snap[index][allkeys[low-1]]
	}
}

func (this *SnapshotArray) Get2(index int, snap_id int) int {
	for snap_id >= 0 {
		if v, ok := this.snap[index][snap_id]; ok {
			return v
		} else {
			snap_id--
		}
	}
	return 0
}


/**
 * Your SnapshotArray object will be instantiated and called as such:
 * obj := Constructor(length);
 * obj.Set(index,val);
 * param_2 := obj.Snap();
 * param_3 := obj.Get(index,snap_id);
 */

python3 解法, 执行用时: 496 ms, 内存消耗: 49.8 MB, 提交时间: 2023-09-08 14:27:32

class SnapshotArray:

    def __init__(self, length: int):
        # 初始化字典数组和 id
        self.arr = [{0: 0} for _ in range(length)]
        self.sid = 0

    def set(self, index: int, val: int) -> None:
        # 设置当前快照的元素值
        self.arr[index][self.sid] = val

    def snap(self) -> int:
        # 每次快照 id 加 1
        self.sid += 1
        # 返回上一个快照 id
        return self.sid - 1

    def get(self, index: int, snap_id: int) -> int:
        # 选择要查找的元素的字典
        d = self.arr[index]
        # 如果快照恰好存在, 直接返回
        if snap_id in d:
            return d[snap_id]
        # 不存在则进行二分搜索, 查找快照前最后一次修改
        k = list(d.keys())
        i = bisect.bisect_left(k, snap_id)
        return d[k[i - 1]]


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)