在未排序的数组中搜索，其中给定元素的范围

Question

我有一个数组，表示为 A，包含整数。这些整数的范围落在区间 [1, 10^6] 内，数组的大小约为 50,000 个元素。我的目标是确定给定的数字是否表示为“x”（其中 1 <= x <= 10^6), exists within the array and, if so, to retrieve its index.

目前，我已经通过维护一个大小为 10^6 的附加数组来实现解决方案。该辅助数组用于将每个元素值映射到数组 A 中相应的索引。虽然这种方法为搜索提供了最佳时间复杂度，但它需要相当大的额外空间，总计 10^6 个单位。我正在寻找一种替代解决方案，该解决方案可以实现相同的功能，同时将所需空间最小化到低于 10^6 的值。

Answer 1

您使用哪种语言？ 在 C# 中你可以使用字典。

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int[] A = { 5, 2, 7, 10, 3, 8, 1, 6, 4, 9 };

        // Create a Dictionary to store the mapping between element value and its index in A
        Dictionary<int, int> indexMap = new Dictionary<int, int>();

        // Populate the Dictionary
        for (int i = 0; i < A.Length; i++)
        {
            // Check if the element already exists in the Dictionary
            if (!indexMap.ContainsKey(A[i]))
            {
                // If not, add it to the Dictionary
                indexMap.Add(A[i], i);
            }
        }

        // Test cases
        int[] testCases = { 3, 8, 11 };

        foreach (int x in testCases)
        {
            if (indexMap.ContainsKey(x))
            {
                Console.WriteLine($"Number {x} found at index {indexMap[x]}");
            }
            else
            {
                Console.WriteLine($"Number {x} not found");
            }
        }
    }
}

说明：

我创建了一个字典“indexMap”，键是元素值，值是其在数组 A 中的索引。

然后我迭代数组 A 并填充字典。

最后，要检查数组中是否存在数字并获取其索引，我们只需检查“indexMap”是否包含该键即可。

或者你可以尝试使用Hashset。

Answer 2

在 C 中你可以尝试这个：

#include <stdio.h>

#define ARRAY_SIZE 50000
#define RANGE 1000000

int main() {
    int A[ARRAY_SIZE] = { 5, 2, 7, 10, 3, 8, 1, 6, 4, 9 };
    int indexMap[RANGE + 1] = {0}; // Initialize indexMap, I fill it zeros

    // Populate indexMap
    for (int i = 0; i < ARRAY_SIZE; i++) {
        indexMap[A[i]] = i + 1; // Store index (here I added 1 just to avoid confusion with zero index)
    }

    // Test cases
    int testCases[] = {3, 8, 11};

    for (int i = 0; i < sizeof(testCases) / sizeof(testCases[0]); i++) {
        int x = testCases[i];
        if (x >= 1 && x <= RANGE && indexMap[x] != 0) {
            printf("Number %d found at index %d\n", x, indexMap[x] - 1); // Remember to Subtract 1 to get the actual index
        } else {
            printf("Number %d not found\n", x);
        }
    }

    return 0;
}

• 我们没有创建大小为 10^6 的数组来存储所有可能整数的映射，而是只为数组 A 中实际存在的整数分配空间。
• 与您在问题描述中尝试的解决方案相比，此方法减少了内存使用量，因为内存仅分配给数组 A 中存在的整数，而不是分配给 1 到 10^6 范围内的所有整数。