hashtable – Huahua’s Tech Road

花花酱 LeetCode 2349. Design a Number Container System

By zxi on March 30, 2025

两个hashtable，一个是index->number，另外一个是number -> {index}，使用treeset，自动排序。

时间复杂度：change O(logn)，find O(1)
空间复杂度：O(n)

class NumberContainers {

public:

NumberContainers() {}

void change(int index, int number) {

if (m_.count(index)) {

auto it = idx_.find(m_[index]);

it->second.erase(index);

if (it->second.empty())

idx_.erase(it);

}

m_[index] = number;

idx_[number].insert(index);

}

int find(int number) {

auto it = idx_.find(number);

if (it == end(idx_)) return -1;

return *begin(it->second);

}

private:

unordered_map<int, int> m_; // index -> num

unordered_map<int, set<int>> idx_; // num -> {index}

};

花花酱 LeetCode 2353. Design a Food Rating System

By zxi on March 29, 2025

Hashtable + TreeSet / OrderedSet

用了三个Hashtable…

菜名 -> 菜系
菜系 -> Treemap
菜名 -> 所在Treemap中的迭代器

每个菜系用一个TreeSet来保存从高到低的菜色排名，查询的时候只要拿出第一个就好了。

修改的时候，拿出迭代器，删除原来的评分，再把新的评分加入（别忘了更新迭代器）

时间复杂度：构造O(nlogn)，修改O(logn)，查询O(1)

空间复杂度：O(n)

class FoodRatings {

public:

FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {

const int n = foods.size();

for (int i = 0; i < n; ++i) {

n_[foods[i]] = cuisines[i];

m_[foods[i]] = c_[cuisines[i]].emplace(-ratings[i], foods[i]).first;

}

void changeRating(string food, int newRating) {

const string& cuisine = n_[food];

c_[cuisine].erase(m_[food]);

m_[food] = c_[cuisine].emplace(-newRating, food).first;

}

string highestRated(string cuisine) {

return begin(c_[cuisine])->second;

}

private:

unordered_map<string, set<pair<int, string>>> c_; // cuisine -> {{-rating, name}}

unordered_map<string, string> n_; // food -> cuisine

unordered_map<string, set<pair<int, string>>::iterator> m_; // food -> set iterator

};

/**

* Your FoodRatings object will be instantiated and called as such:

* FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);

* obj->changeRating(food,newRating);

* string param_2 = obj->highestRated(cuisine);

花花酱 LeetCode 3242. Design Neighbor Sum Service

By zxi on March 29, 2025

青铜 Brute Force：每次需要花费O(n*n)的时间去查找query所在的格子，求和是O(1)。总的时间复杂度达到O(n^4)，肯定会超时。

白银 Hashtable：由于所有元素的值的唯一的，我们可以使用hashtable（或者数组）来记录value所在的格子坐标，这样每次Query都是O(1)时间。
时间复杂度：初始化O(n^2)，query O(1)。
空间复杂度：O(n^2)

class NeighborSum {

public:

NeighborSum(vector<vector<int>>& grid):

n_(grid.size()), g_(&grid), xy_(n_ * n_) {

for (int i = 0; i < n_; ++i)

for (int j = 0; j < n_; ++j)

xy_[grid[i][j]] = {j, i};

}

int adjacentSum(int value) {

auto [x, y] = xy_[value];

return val(x, y - 1) + val(x, y + 1) + val(x + 1, y) + val(x - 1, y);

}

int diagonalSum(int value) {

auto [x, y] = xy_[value];

return val(x - 1, y - 1) + val(x - 1, y + 1) + val(x + 1, y - 1) + val(x + 1, y + 1);

}

private:

inline int val(int x, int y) const {

if (x < 0 || x >= n_ || y < 0 || y >= n_) return 0;

return (*g_)[y][x];

}

int n_;

vector<vector<int>>* g_;

vector<pair<int, int>> xy_;

};

黄金 Precompute：在初始化的时候顺便求合，开两个数组一个存上下左右的，一个存对角线的。query的时候直接返回答案就可以了。
时间复杂度和白银是一样的，但会快一些（省去了求合的过程）。

class NeighborSum {

public:

NeighborSum(vector<vector<int>>& grid) {

int n = grid.size();

adj_.resize(n * n);

dia_.resize(n * n);

auto v = [&](int x, int y) -> int {

if (x < 0 || x >= n || y < 0 || y >= n)

return 0;

return grid[y][x];

};

for (int y = 0; y < n; ++y)

for (int x = 0; x < n; ++x) {

adj_[grid[y][x]] = v(x, y - 1) + v(x, y + 1) + v(x + 1, y) + v(x - 1, y);

dia_[grid[y][x]] = v(x - 1, y - 1) + v(x - 1, y + 1) + v(x + 1, y - 1) + v(x + 1, y + 1);

}

int adjacentSum(int value) {

return adj_[value];

}

int diagonalSum(int value) {

return dia_[value];

}

private:

vector<int> adj_;

vector<int> dia_;

};

花花酱 LeetCode 3408. Design Task Manager

By zxi on March 27, 2025

pq_ 使用std::map充当优先队列，存储(priority, taskId) -> userId
m_ 使用std::unordered_map，存储taskId -> pq_的迭代器

所有操作都是O(logn)

class TaskManager {

public:

TaskManager(vector<vector<int>>& tasks) {

for (const auto& task : tasks)

add(task[0], task[1], task[2]);

}

void add(int userId, int taskId, int priority) {

m_[taskId] = pq_.emplace(make_pair(priority, taskId), userId).first;

}

void edit(int taskId, int newPriority) {

const int userId = m_[taskId]->second;

rmv(taskId);

add(userId, taskId, newPriority);

}

void rmv(int taskId) {

auto it = m_.find(taskId);

pq_.erase(it->second);

m_.erase(it);

}

int execTop() {

if (pq_.empty()) return -1;

auto it = pq_.rbegin();

const int userId = it->second;

const int taskId = (it->first.second);

rmv(taskId);

return userId;

}

private:

map<std::pair<int,int>, int> pq_; // (priority, taskId) -> userId;

unordered_map<int, map<std::pair<int,int>, int>::iterator> m_; // taskId -> pq iterator

};

花花酱 LeetCode 3005. Count Elements With Maximum Frequency

By zxi on January 15, 2024

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.

Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution: Hashtable

Use a hashtable to store the frequency of each element, and compare it with a running maximum frequency. Reset answer if current frequency is greater than maximum frequency. Increment the answer if current frequency is equal to the maximum frequency.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxFrequencyElements(vector<int>& nums) {

unordered_map<int, int> m;

int freq = 0;

int ans = 0;

for (int x : nums) {

if (++m[x] > freq)

freq = m[x], ans = 0;

if (m[x] == freq)

ans += m[x];

}

return ans;

}

};

Posts tagged as “hashtable”

花花酱 LeetCode 2349. Design a Number Container System

花花酱 LeetCode 2353. Design a Food Rating System

花花酱 LeetCode 3242. Design Neighbor Sum Service

花花酱 LeetCode 3408. Design Task Manager

花花酱 LeetCode 3005. Count Elements With Maximum Frequency

Solution: Hashtable

C++