Posts published in “Hashtable”

花花酱 LeetCode 1. Two Sum

By zxi on November 23, 2017

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea:

Brute force / Hashtable

Solution1:

Brute force / C++

Time complexity: O(n^2)

Space complexity: O(1)

// Author: Huahua

// Runtime: 166 ms

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

for (int i = 0; i < nums.size(); ++i) {

for (int j = i + 1;j < nums.size(); ++j) {

int sum = nums[i] + nums[j];

if (sum == target) {

return {i, j};

}

return {};

}

};

Solution 2:

Hashtable / C++

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> indies;

for (int i = 0; i < nums.size(); ++i)

indies[nums[i]] = i;

for (int i = 0; i < nums.size(); ++i) {

int left = target - nums[i];

if (indies.count(left) && indies[left] != i) {

return {i, indies[left]};

}

return {};

}

};

花花酱 LeetCode 169. Majority Element

By zxi on November 4, 2017

题目大意：给你一个数组，其中一个数出现超过n/2次，问你出现次数最多的那个数是什么？

Problem:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Ideas:

Solution 1:

Hash table O(n) / O(n)

// Author: Huahua

// Runtime : 23 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

unordered_map<int, int> count;

const int n = nums.size();

for (const int num : nums)

if (++count[num] > n / 2) return num;

return -1;

}

};

Solution 2:

BST O(nlogk) / O(n)

// Author: Huahua

// Runtime : 19 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

map<int, int> count;

const int n = nums.size();

for (const int num : nums)

if (++count[num] > n / 2) return num;

return -1;

}

};

Solution 3:

Randomization O(n) / O(1)

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

srand(time(nullptr));

const int n = nums.size();

while (true) {

const int index = rand() % n;

const int majority = nums[index];

int count = 0;

for (const int num : nums)

if (num == majority && ++count > n/2) return num;

}

return -1;

}

};

Solution 4:

Bit voting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

const int n = nums.size();

int majority = 0;

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

int mask = 1 << i;

int count = 0;

for (const int num : nums)

if ((num & mask) && (++count > n /2)) {

majority |= mask;

break;

}

return majority;

}

};

Solution 5:

Moore Voting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

int majority = nums.front();

int count = 0;

for (const int num : nums) {

if (num == majority) ++count;

else if (--count == 0) {

count = 1;

majority = num;

}

return majority;

}

};

Solution 6:

Full sorting O(nlogn) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

std::sort(nums.begin(), nums.end());

return nums[nums.size()/2];

}

};

Solution 7:

Partial sorting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());

return nums[nums.size() / 2];

}

};

Solution 8:

Divide and conquer O(nlogn) / O(logn)

class Solution {

public:

int majorityElement(vector<int>& nums) {

return majorityElement(nums, 0, nums.size() - 1);

}

private:

int majorityElement(const vector<int>& nums, int l, int r) {

if (l == r) return nums[l];

const int m = l + (r - l) / 2;

const int ml = majorityElement(nums, l, m);

const int mr = majorityElement(nums, m + 1, r);

if (ml == mr) return ml;

return count(nums.begin() + l, nums.begin() + r + 1, ml) >

count(nums.begin() + l, nums.begin() + r + 1, mr)

? ml : mr;

}

};

Divide and conquer O(nlogn) / O(logn)

class Solution {

public:

int majorityElement(vector<int>& nums) {

return majorityElement(nums, 0, nums.size() - 1).first;

}

private:

pair<int, int> majorityElement(const vector<int>& nums, int l, int r) {

if (l == r) return {nums[l], 1};

int mid = l + (r - l) / 2;

auto ml = majorityElement(nums, l, mid);

auto mr = majorityElement(nums, mid + 1, r);

if (ml.first == mr.first) return { ml.first, ml.second + mr.second };

if (ml.second > mr.second)

return { ml.first, ml.second + count(nums.begin() + mid + 1, nums.begin() + r + 1, ml.first) };

else

return { mr.first, mr.second + count(nums.begin() + l, nums.begin() + mid + 1, mr.first) };

}

};

花花酱 LeetCode 347. Top K Frequent Elements

By zxi on October 22, 2017

Problem:

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Idea:

Solution 2: Priority queue / max heap

Time complexity: O(n) + O(nlogk)

Space complexity: O(n)

C++

// Author: Huahuas

// Running time: 16 ms

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

priority_queue<pair<int, int>> q;

for (const auto& pair : count) {

q.emplace(-pair.second, pair.first);

if (q.size() > k) q.pop();

}

vector<int> ans;

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

ans.push_back(q.top().second);

q.pop();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 56 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> x[0] - y[0]);

for (Integer num : counts.keySet()) {

queue.offer(new int[]{counts.get(num), num});

if (queue.size() > k) queue.poll();

}

List<Integer> ans = new ArrayList<>();

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

ans.add(queue.poll()[1]);

return ans;

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

h = []

for num in counts.keys():

heapq.heappush(h, (counts[num], num))

if len(h) > k: heapq.heappop(h)

return [heapq.heappop(h)[1] for i in range(k)]

Solution 3: Bucket Sort

Time complexity: O(n)

Space complexity: O(n)

C++/hashmap

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

int max_freq = 1;

for (const int num : nums)

max_freq = max(max_freq, ++count[num]);

map<int, vector<int>> buckets;

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (int i = max_freq; i >= 1; --i) {

auto it = buckets.find(i);

if (it == buckets.end()) continue;

ans.insert(ans.end(), it->second.begin(), it->second.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

C++/array

class Solution {

public:

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

vector<vector<int>> buckets(nums.size() + 1);

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (auto it = buckets.rbegin(); it != buckets.rend(); ++it) {

const vector<int>& keys = *it;

if (keys.empty()) continue;

ans.insert(ans.begin(), keys.begin(), keys.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 23 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

List[] buckets = new List[nums.length + 1];

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

for (int num : counts.keySet()) {

int count = counts.get(num);

if (buckets[count] == null)

buckets[count] = new ArrayList<Integer>();

buckets[count].add(num);

}

List<Integer> ans = new ArrayList<>();

for (int i = buckets.length - 1; i > 0 && ans.size() < k; --i) {

if (buckets[i] != null) ans.addAll(buckets[i]);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

buckets = [[] for _ in range(len(nums) + 1)]

for num in counts.keys():

buckets[counts[num]].append(num)

ans = []

for i in range(len(nums), 0, -1):

ans += buckets[i]

if len(ans) == k: return ans

return ans

Solution1: Heap

C++

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

class Solution {

public:

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

// events, x, h, id, type (1=entering, -1=leaving)

vector<Event> events;

int id = 0;

for (const auto& b : buildings) {

events.push_back(Event{id, b[0], b[2], 1});

events.push_back(Event{id, b[1], b[2], -1});

++id;

}

// Sort events by x

sort(events.begin(), events.end());

// Init the heap

MaxHeap heap(buildings.size());

vector<pair<int, int>> ans;

// Process all the events

for (const auto& event: events) {

int x = event.x;

int h = event.h;

int id = event.id;

int type = event.type;

if (type == 1) {

if (h > heap.Max())

ans.emplace_back(x, h);

heap.Add(h, id);

} else {

heap.Remove(id);

if (h > heap.Max())

ans.emplace_back(x, heap.Max());

}

return ans;

}

private:

struct Event {

int id;

int x;

int h;

int type;

// sort by x+, type-, h,

bool operator<(const Event& e) const {

if (x == e.x)

// Entering event h from large to small

// Leaving event h from small to large

return type * h > e.type * e.h;

return x < e.x;

}

};

class MaxHeap {

public:

MaxHeap(int max_items):

idx_(max_items, -1), vals_(max_items), size_(0) {}

// Add an item into the heap. O(log(n))

void Add(int key, int id) {

idx_[id] = size_;

vals_[size_] = {key, id};

++size_;

HeapifyUp(idx_[id]);

}

// Remove an item. O(log(n))

void Remove(int id) {

int idx_to_evict = idx_[id];

// swap with the last element

SwapNode(idx_to_evict, size_ - 1);

--size_;

HeapifyDown(idx_to_evict);

}

bool Empty() const {

return size_ == 0;

}

// Return the max of heap

int Max() const {

return Empty() ? 0 : vals_.front().first;

}

private:

void SwapNode(int i, int j) {

if (i == j) return;

std::swap(idx_[vals_[i].second], idx_[vals_[j].second]);

std::swap(vals_[i], vals_[j]);

}

void HeapifyUp(int i) {

while (i != 0) {

int p = (i - 1) / 2;

if (vals_[i].first <= vals_[p].first)

return;

SwapNode(i, p);

i = p;

}

// Make the heap valid again. O(log(n))

void HeapifyDown(int i) {

while (true) {

int c1 = i*2 + 1;

int c2 = i*2 + 2;

// No child

if (c1 >= size_) return;

// Get the index of the max child

int c = (c2 < size_

&& vals_[c2].first > vals_[c1].first ) ? c2 : c1;

// If key[c] is greater than key[i], swap them and

// continue to HeapifyDown(c)

if (vals_[c].first <= vals_[i].first)

return;

SwapNode(c, i);

i = c;

}

// {key, id}

vector<pair<int,int>> vals_;

// Index of the i-th item in vals_

vector<int> idx_;

int size_;

};

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

// Author: Huahua

// Running time: 91 ms (beats 79.1%)

class Solution {

private MaxHeap heap;

public List<int[]> getSkyline(int[][] buildings) {

int n = buildings.length;

// {x, h, id}

ArrayList<int[]> es = new ArrayList<int[]>();

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

es.add(new int[]{ buildings[i][0], buildings[i][2], i});

es.add(new int[]{ buildings[i][1], -buildings[i][2], i});

}

es.sort((e1, e2) -> {

return e1[0] == e2[0] ? e2[1] - e1[1] : e1[0] - e2[0]; });

List<int[]> ans = new ArrayList<int[]>();

heap = new MaxHeap(n);

for (int[] e : es) {

int x = e[0];

int h = e[1];

int id = e[2];

Boolean entering = h > 0;

h = Math.abs(h);

if (entering) {

if (h > heap.max())

ans.add(new int[]{x, h});

heap.add(h, id);

} else {

heap.remove(id);

if (h > heap.max())

ans.add(new int[]{x, heap.max()});

}

return ans;

}

private class MaxHeap {

// (key, id)

private List<int[]> nodes;

// idx[i] = index of building[i] in nodes

private int[] idx;

public MaxHeap(int size) {

idx = new int[size];

nodes = new ArrayList<int[]>();

}

public void add(int key, int id) {

idx[id] = nodes.size();

nodes.add(new int[]{key, id});

heapifyUp(idx[id]);

}

public void remove(int id) {

int idx_to_evict = idx[id];

swapNode(idx_to_evict, nodes.size() - 1);

idx[id] = -1;

nodes.remove(nodes.size() - 1);

heapifyUp(idx_to_evict);

heapifyDown(idx_to_evict);

}

public Boolean empty() {

return nodes.isEmpty();

}

public int max() {

return empty() ? 0 : nodes.get(0)[0];

}

private void heapifyUp(int i) {

while (i != 0) {

int p = (i - 1) / 2;

if (nodes.get(i)[0] <= nodes.get(p)[0])

return;

swapNode(i, p);

i = p;

}

private void swapNode(int i, int j) {

int tmpIdx = idx[nodes.get(i)[1]];

idx[nodes.get(i)[1]] = idx[nodes.get(j)[1]];

idx[nodes.get(j)[1]] = tmpIdx;

int[] tmpNode = nodes.get(i);

nodes.set(i, nodes.get(j));

nodes.set(j, tmpNode);

}

private void heapifyDown(int i) {

while (true) {

int c1 = i*2 + 1;

int c2 = i*2 + 2;

if (c1 >= nodes.size()) return;

int c = (c2 < nodes.size()

&& nodes.get(c2)[0] > nodes.get(c1)[0]) ? c2 : c1;

if (nodes.get(c)[0] <= nodes.get(i)[0])

return;

swapNode(c, i);

i = c;

}

Solution 2: Multiset

C++

// Author: Huahua

// Time Complexity: O(nlogn)

// Space Complexity: O(n)

// Running Time: 22 ms

class Solution {

public:

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

typedef pair<int, int> Event;

// events, x, h

vector<Event> es;

hs_.clear();

for (const auto& b : buildings) {

es.emplace_back(b[0], b[2]);

es.emplace_back(b[1], -b[2]);

}

// Sort events by x

sort(es.begin(), es.end(), [](const Event& e1, const Event& e2){

if (e1.first == e2.first) return e1.second > e2.second;

return e1.first < e2.first;

});

vector<pair<int, int>> ans;

// Process all the events

for (const auto& e: es) {

int x = e.first;

bool entering = e.second > 0;

int h = abs(e.second);

if (entering) {

if (h > this->maxHeight())

ans.emplace_back(x, h);

hs_.insert(h);

} else {

hs_.erase(hs_.equal_range(h).first);

if (h > this->maxHeight())

ans.emplace_back(x, this->maxHeight());

}

return ans;

}

private:

int maxHeight() const {

if (hs_.empty()) return 0;

return *hs_.rbegin();

}

multiset<int> hs_;

};

Posts published in “Hashtable”

花花酱 LeetCode 1. Two Sum

花花酱 LeetCode 169. Majority Element

花花酱 LeetCode 347. Top K Frequent Elements

Solution 2: Priority queue / max heap

C++

Java

Python

Solution 3: Bucket Sort

C++/hashmap

C++/array

Java

Python

Related Problems

花花酱 LeetCode 128. Longest Consecutive Sequence

花花酱 LeetCode 218. The Skyline Problem

Solution1: Heap

C++

Java

Solution 2: Multiset

C++