不使用库或哈希表实现稀疏数组的最优方案咨询

你的思路核心方向是对的，但维护zero_indices_arr完全是多余的——因为稀疏数组的默认值就是0，不需要额外存储零元素的索引，只需要专注维护非零元素的索引和值即可，这样能大幅简化实现逻辑，同时优化操作效率。

原思路的问题 #

你维护三个数组的方式，需要在set操作时同时处理零和非零两个索引数组，不仅代码繁琐，而且数组切片/插入删除的O(n)时间复杂度是基于原数组长度n的，而稀疏数组的非零元素数量k远小于n，这部分开销其实可以进一步降低。

最优实现方案：双有序数组 #

只需要两个严格递增的数组：

• self.indices：存储所有非零元素的索引，保持升序
• self.values：存储对应indices位置的非零值

各操作的时间复杂度 #

• 构造函数：O(n)，遍历原数组一次，仅记录非零元素的索引和值
• get方法：O(log k)，k是当前非零元素的数量，在indices中二分查找目标索引，找到则返回对应值，否则返回0
• set方法：O(log k + k)，二分查找定位后，仅对长度为k的数组进行插入/删除/更新操作，k远小于n，实际效率远优于原思路的O(log n +n)

Python代码实现 #

class SparseArray:
    def __init__(self, original):
        self.indices = []
        self.values = []
        self.length = len(original)
        # 遍历原数组，收集非零元素
        for idx, val in enumerate(original):
            if val != 0:
                self.indices.append(idx)
                self.values.append(val)
    
    def get(self, i):
        if i < 0 or i >= self.length:
            raise IndexError("Index out of bounds")
        # 二分查找目标索引
        left, right = 0, len(self.indices) - 1
        while left <= right:
            mid = (left + right) // 2
            if self.indices[mid] == i:
                return self.values[mid]
            elif self.indices[mid] < i:
                left = mid + 1
            else:
                right = mid - 1
        # 没找到，返回默认值0
        return 0
    
    def set(self, i, val):
        if i < 0 or i >= self.length:
            raise IndexError("Index out of bounds")
        left, right = 0, len(self.indices) - 1
        pos = len(self.indices)  # 默认插入到末尾
        # 二分查找定位位置
        while left <= right:
            mid = (left + right) // 2
            if self.indices[mid] == i:
                # 找到对应索引，更新或删除
                if val == 0:
                    # 值设为0，删除该元素
                    del self.indices[mid]
                    del self.values[mid]
                else:
                    self.values[mid] = val
                return
            elif self.indices[mid] < i:
                left = mid + 1
            else:
                pos = mid
                right = mid - 1
        # 没找到索引，且val非0，插入新元素
        if val != 0:
            self.indices.insert(pos, i)
            self.values.insert(pos, val)

方案优势 #

1. 逻辑简洁：不需要维护零元素的索引，减少一半的状态维护工作
2. 效率更高：所有操作的时间复杂度都基于非零元素数量k，而非原数组长度n，符合稀疏数组的场景特性
3. 边界处理清晰：直接通过数组长度判断索引越界，逻辑直观

内容的提问来源于stack exchange，提问作者Kang_the_Conqueror