Массив как хеш-таблица

В этом уроке ты

Научишься делать выбор между массивом и хеш-таблицей.
Решишь задачу с реального собеседования в крупной IT-компании (BigTech).

Подсчет общего префикса

Хеш-таблицы — это мощный инструмент, но в некоторых случаях их можно заменить на массивы для ускорения времени работы программы. Рассмотрим это на примере задачи подсчета общего префикса в двух массивах.

Условие

Даны два целочисленных массива nums1 и nums2 длины n. Оба массива содержат только числа от 1 до n включительно, при этом каждое число обязательно встречается ровно один раз в каждом из массивов.

Нужно найти общий префиксный массив для nums1 и nums2.

Пример

Ввод: nums1 = [2,1,3,4,5], nums2 = [3,1,2,5,4]
Вывод: [0,1,3,3,5]
Объяснение:
0 = [2] и [3] имеют 0 общих элементов
1 = [2,1] и [3,1] имеют 1 общий элемент (1)
3 = [2,1,3] и [3,1,2] имеют 3 общих элемента (1,2,3)
3 = [2,1,3,4] и [3,1,2,5] имеют 3 общих элемента (1,2,3)
5 = [2,1,3,4,5] и [3,1,2,5,4] имеют 5 общих элементов (1,2,3,4,5)

Решение с использованием хеш-таблицы

public class Solution
{
    public static List<int> FindCommonPrefix(List<int> nums1, List<int> nums2)
    {
        int n = nums1.Count;
        List<int> prefixCommonArray = new List<int>(new int[n]);

        // Используем Dictionary для подсчета количества встреченных элементов
        Dictionary<int, int> countMap = new Dictionary<int, int>();
        int commonCount = 0;

        for (int i = 0; i < n; i++)
        {
            // Ключ — элемент массива, значение — количество повторений
            if (!countMap.ContainsKey(nums1[i]))
                countMap[nums1[i]] = 0;
            countMap[nums1[i]]++;
            // Если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
            if (countMap[nums1[i]] == 2)
                commonCount++;

            if (!countMap.ContainsKey(nums2[i]))
                countMap[nums2[i]] = 0;
            countMap[nums2[i]]++;
            // Если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
            if (countMap[nums2[i]] == 2)
                commonCount++;

            // Сохраняем количество общих элементов на текущем индексе
            prefixCommonArray[i] = commonCount;
        }

        return prefixCommonArray;
    }
}

#include <vector>
#include <unordered_map>

using namespace std;

vector<int> findCommonPrefix(const vector<int>& nums1, const vector<int>& nums2) {
    int n = nums1.size();
    vector<int> prefixCommonArray(n, 0);

    // используем unordered_map для подсчета количества встреченных элементов
    unordered_map<int, int> countMap;
    int commonCount = 0;

    for (int i = 0; i < n; i++) {
        // ключ — элемент массива, значение — количество повторений
        countMap[nums1[i]]++;
        // если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
        if (countMap[nums1[i]] == 2) {
            commonCount++;
        }

        countMap[nums2[i]]++;
        // если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
        if (countMap[nums2[i]] == 2) {
            commonCount++;
        }

        // сохраняем количество общих элементов на текущем индексе
        prefixCommonArray[i] = commonCount;
    }

    return prefixCommonArray;
}

package main

func findCommonPrefix(nums1 []int, nums2 []int) []int {
    n := len(nums1)
    prefixCommonArray := make([]int, n)

    // используем map для подсчета количества встреченных элементов
    countMap := make(map[int]int)
    commonCount := 0

    for i := 0; i < n; i++ {
        // ключ — элемент массива, значение — количество повторений
        countMap[nums1[i]]++
        // если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
        if countMap[nums1[i]] == 2 {
            commonCount++
        }

        countMap[nums2[i]]++
        // если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
        if countMap[nums2[i]] == 2 {
            commonCount++
        }

        // сохраняем количество общих элементов на текущем индексе
        prefixCommonArray[i] = commonCount
    }

    return prefixCommonArray
}

import java.util.*;

public class Solution {
    public List<Integer> findCommonPrefix(List<Integer> nums1, List<Integer> nums2) {
        int n = nums1.size();
        List<Integer> prefixCommonArray = new ArrayList<>();

        // используем HashMap для подсчета количества встреченных элементов
        HashMap<Integer, Integer> countMap = new HashMap<>();
        int commonCount = 0;

        for (int i = 0; i < n; i++) {
            // ключ — элемент массива, значение — количество повторений
            countMap.merge(nums1.get(i), 1, Integer::sum);
            // если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
            if (countMap.get(nums1.get(i)) == 2) {
                commonCount++;
            }

            countMap.merge(nums2.get(i), 1, Integer::sum);
            // если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
            if (countMap.get(nums2.get(i)) == 2) {
                commonCount++;
            }

            // сохраняем количество общих элементов на текущем индексе
            prefixCommonArray.add(commonCount);
        }

        return prefixCommonArray;
    }
}

from typing import *
from collections import defaultdict

def find_common_prefix(nums1: List[int], nums2: List[int]) -> List[int]:
    n = len(nums1)
    prefix_common_array = [0] * n

    # используем defaultdict для подсчета количества встреченных элементов
    count_map = defaultdict(int)
    common_count = 0

    for i in range(n):
        # ключ — элемент массива, значение — количество повторений
        count_map[nums1[i]] += 1
        # если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
        if count_map[nums1[i]] == 2:
            common_count += 1

        count_map[nums2[i]] += 1
        # если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
        if count_map[nums2[i]] == 2:
            common_count += 1

        # сохраняем количество общих элементов на текущем индексе
        prefix_common_array[i] = common_count

    return prefix_common_array

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @returns {number[]}
 */
export function findCommonPrefix(nums1, nums2) {
  const n = nums1.length;
  const prefixCommonArray = new Array(n).fill(0);

  // используем объект для подсчета количества встреченных элементов
  const countMap = {};
  let commonCount = 0;

  for (let i = 0; i < n; i++) {
    // ключ — элемент массива, значение — количество повторений
    countMap[nums1[i]] = (countMap[nums1[i]] || 0) + 1;
    // если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
    if (countMap[nums1[i]] === 2) {
      commonCount++;
    }

    countMap[nums2[i]] = (countMap[nums2[i]] || 0) + 1;
    // если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
    if (countMap[nums2[i]] === 2) {
      commonCount++;
    }

    // сохраняем количество общих элементов на текущем индексе
    prefixCommonArray[i] = commonCount;
  }

  return prefixCommonArray;
}

Решение использует хеш-таблицу для отслеживания частоты появления элементов из обоих массивов на каждом индексе. Для каждого индекса проверяется, встречались ли элементы из одного массива в другом, и, если это так, увеличивается счетчик общих элементов. В результате для каждого индекса возвращается количество общих элементов в префиксах обоих массивов.

Решение с использованием массива

public class Solution
{
    public static List<int> FindCommonPrefix(List<int> nums1, List<int> nums2)
    {
        int n = nums1.Count;
        List<int> prefixCommonArray = new List<int>(new int[n]);

        // Используем массив вместо хеш-таблицы для подсчета встреченных элементов
        int[] frequency = new int[n + 1];
        int commonCount = 0;

        for (int i = 0; i < n; i++)
        {
            frequency[nums1[i]]++;
            // Если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
            if (frequency[nums1[i]] == 2)
                commonCount++;

            frequency[nums2[i]]++;
            // Если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
            if (frequency[nums2[i]] == 2)
                commonCount++;

            // Сохраняем количество общих элементов на текущем индексе
            prefixCommonArray[i] = commonCount;
        }

        return prefixCommonArray;
    }
}

#include <vector>

using namespace std;

vector<int> findCommonPrefix(const vector<int>& nums1, const vector<int>& nums2) {
    int n = nums1.size();
    vector<int> prefixCommonArray(n, 0);

    // используем массив вместо хеш-таблицы для подсчета встреченных элементов
    vector<int> frequency(n + 1, 0);
    int commonCount = 0;

    for (int i = 0; i < n; i++) {
        frequency[nums1[i]]++;
        // если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
        if (frequency[nums1[i]] == 2) {
            commonCount++;
        }

        frequency[nums2[i]]++;
        // если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
        if (frequency[nums2[i]] == 2) {
            commonCount++;
        }

        // сохраняем количество общих элементов на текущем индексе
        prefixCommonArray[i] = commonCount;
    }

    return prefixCommonArray;
}

package main

func findCommonPrefix(nums1 []int, nums2 []int) []int {
    n := len(nums1)
    prefixCommonArray := make([]int, n)

    // используем массив вместо хеш-таблицы для подсчета встреченных элементов
    frequency := make([]int, n+1)
    commonCount := 0

    for i := 0; i < n; i++ {
        frequency[nums1[i]]++
        // если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
        if frequency[nums1[i]] == 2 {
            commonCount++
        }

        frequency[nums2[i]]++
        // если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
        if frequency[nums2[i]] == 2 {
            commonCount++
        }

        // сохраняем количество общих элементов на текущем индексе
        prefixCommonArray[i] = commonCount
    }

    return prefixCommonArray
}

import java.util.*;

public class Solution {
    public List<Integer> findCommonPrefix(List<Integer> nums1, List<Integer> nums2) {
        int n = nums1.size();
        List<Integer> prefixCommonArray = new ArrayList<>();

        // используем массив вместо хеш-таблицы для подсчета встреченных элементов
        int[] frequency = new int[n + 1];
        int commonCount = 0;

        for (int i = 0; i < n; i++) {
            int a = nums1.get(i);
            int b = nums2.get(i);

            frequency[a]++;
            // если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
            if (frequency[a] == 2) {
                commonCount++;
            }

            frequency[b]++;
            // если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
            if (frequency[b] == 2) {
                commonCount++;
            }

            // сохраняем количество общих элементов на текущем индексе
            prefixCommonArray.add(commonCount);
        }

        return prefixCommonArray;
    }
}

from typing import *

def find_common_prefix(nums1: List[int], nums2: List[int]) -> List[int]:
    n = len(nums1)
    prefix_common_array = [0] * n

    # используем массив вместо хеш-таблицы для подсчета встреченных элементов
    frequency = [0] * (n + 1)
    common_count = 0

    for i in range(n):
        frequency[nums1[i]] += 1
        # если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
        if frequency[nums1[i]] == 2:
            common_count += 1

        frequency[nums2[i]] += 1
        # если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
        if frequency[nums2[i]] == 2:
            common_count += 1

        # сохраняем количество общих элементов на текущем индексе
        prefix_common_array[i] = common_count

    return prefix_common_array

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @returns {number[]}
 */
export function findCommonPrefix(nums1, nums2) {
  const n = nums1.length;
  const prefixCommonArray = new Array(n).fill(0);

  // используем массив вместо хеш-таблицы для подсчета встреченных элементов
  const frequency = new Array(n + 1).fill(0);
  let commonCount = 0;

  for (let i = 0; i < n; i++) {
    frequency[nums1[i]]++;
    // если элемент из nums1 уже встречался в nums2, увеличиваем общий счетчик
    if (frequency[nums1[i]] === 2) {
      commonCount++;
    }

    frequency[nums2[i]]++;
    // если элемент из nums2 уже встречался в nums1, увеличиваем общий счетчик
    if (frequency[nums2[i]] === 2) {
      commonCount++;
    }

    // сохраняем количество общих элементов на текущем индексе
    prefixCommonArray[i] = commonCount;
  }

  return prefixCommonArray;
}

Логика решения аналогична предыдущему, но вместо хеш-таблицы используется массив frequency, где индекс элемента массива соответствует его значению, а значение в массиве — это количество встреч данного элемента в обоих массивах.

Когда массивы лучше хеш-таблиц?

Когда данные ограничены диапазоном: Если данные имеют заранее известный и ограниченный диапазон (например, числа от 1 до n), то массивы оказываются значительно более эффективными.
Когда важна производительность и использование памяти: Массивы предлагают более компактное представление данных и более высокую производительность благодаря прямому доступу по индексам.

Да, это все относится к не асимптотической оптимизации, поэтому можно решать и через хеш-таблицы, но интервьюер обязательно оценит такой подход.

Массив как хеш-таблица – это просто не асимптотическая оптимизация за счет замены хеш-таблицы на массив при определенных условиях. Так же показывает продвинутые знания кандидата на собеседовании.

Что дальше

Когда будешь решать задачи на тему "массив как хеш-таблица", обязательно попробуй заменить хеш-таблицу на массив, чтобы лучше усвоить этот паттерн. И скорее переходи к практике!