如何遍历固定大小的稀疏数组并输出非空元素？

Great question! When dealing with sparse arrays (which is exactly what you've got here—most positions are null), a full linear scan from 0 to 149 is definitely inefficient, especially as the array size grows and sparsity increases. Here are several practical, more efficient solutions tailored to different scenarios:

1. Maintain a Secondary Metadata Structure #

The most straightforward optimization is to track non-null elements as you modify the array/hash table. This way, you don't have to scan the entire structure later—you just iterate over your pre-built list of valid entries.

For example:

• When you set arr[3] = 5, add a tuple (3, 5) to a dynamic list (like a Python list or Java ArrayList).
• When you set a position back to null, remove the corresponding entry from the list.

To print non-null elements, simply loop through this list:

# Example in Python
sparse_arr = [None] * 150
sparse_arr[3] = 5
sparse_arr[16] = 22
sparse_arr[127] = 3

# Maintain metadata list
non_null_entries = []
non_null_entries.append((3, 5))
non_null_entries.append((16, 22))
non_null_entries.append((127, 3))

# Print efficiently
for idx, val in non_null_entries:
    print(f"arr[{idx}] = {val}")

This approach runs in O(k) time where k is the number of non-null elements, which is way better than O(n) for large sparse arrays.

2. Leverage Hash Table Built-In Iteration (If Using a Hash Table) #

If you're actually using a hash table (not a fixed-size array), most programming languages provide built-in methods to iterate over only the existing key-value pairs—no need to check every possible index.

For example, in Python:

sparse_hash = {}
sparse_hash[3] = 5
sparse_hash[16] = 22
sparse_hash[127] = 3

# Iterate only existing entries
for key, val in sparse_hash.items():
    print(f"hash[{key}] = {val}")

In Java, you'd use hashMap.entrySet() to loop through valid entries directly. This avoids wasting cycles on non-existent keys (the equivalent of your null array positions).

3. Use a Bitmap for Memory-Efficient Tracking (For Fixed-Size Arrays) #

If you need to minimize extra memory usage, a bitmap is a great alternative to a full list of entries. Each bit in the bitmap represents whether the corresponding array index has a non-null value:

• Set the i-th bit to 1 when arr[i] is assigned a non-null value.
• Set it back to 0 when arr[i] is set to null.

When printing, you scan the bitmap to find all set bits, then retrieve the values from the array at those indices. For a 150-element array, the bitmap only needs ~20 bytes (150 bits = 18.75 bytes), which is negligible.

Caveats to Consider #

• If your array is not very sparse (e.g., most positions have values), a full linear scan might actually be more efficient—maintaining metadata structures adds small overhead for each modification. Always benchmark against your actual use case!
• Make sure to keep your metadata structure in sync with the array/hash table. If you forget to update it when modifying values, you'll get incorrect results.

Hope these solutions help you optimize your traversal!

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