It's the Xinrui Ma

Blog

Tag: HashTable

Top K Frequent Elements

Posted by in LeetCode on

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.

Solution: (key idea, sort the hashtable)
1. create a hashtable, key is the number in array, value is how many times they appear in the array.
2. create an array based on the hashtable, sort the array based on the value
3. slice the array to k size
4. generate the result array

204. Count Primes

Posted by in LeetCode on

Count the number of prime numbers less than a non-negative number, n.

Example:

Key idea is to constructure an array, which at array[i], indicate number i is prime or not.
1. We init the array, and assume all the numbers are prime at first.
2. We start from i = 2, loop through 2 to n
3. Inside every loop, we set the mutiple of i (represent as J) to false. we can set J at j = i * i;

The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don’t let that name scare you, I promise that the concept is surprisingly simple.


Sieve of Eratosthenes: algorithm steps for primes below 121. “Sieve of Eratosthenes Animation” by SKopp is licensed under CC BY 2.0.

We start off with a table of n numbers. Let’s look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, … must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?

4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, … can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?

In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, … Now what should be the terminating loop condition?

It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3? Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime. Solution 1:

Solution 2:

350. Intersection of Two Arrays II — LeetCode

Posted by in LeetCode on

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.
Follow up:
What if the given array is already sorted? How would you optimize your algorithm?
What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution1: Hashtable
Count how many times each digit appears in nums1, store in hash table, where key is the number in array, value is the times.
Then iterate through nums2 array, if the number in nums2 is key of the hashtable, then check if the value larger then 1, if yes, store that number to result array.

387. First Unique Character in a String

Posted by in LeetCode on

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.

Note: You may assume the string contain only lowercase letters.

Solution:

Easy one: Loop through the string twice, find the first one that is no-repeat, return the index.

Using Hashtable.

409. Longest Palindrome

Posted by in LeetCode on

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Solution:
The key to solve this problem is,

If an element appears odd times, add the times minus one.
If an element appears even times, add the times.
If there is an element appears odd times, add 1 to final result.

Two Sum

Posted by in LeetCode on

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution in Java, version 1:
Time complexity in worst case: O(n^2).

Better Solution in Java, using HashTable.

Time complexity depends on the put and get operations of HashMap which is normally O(1).

Time complexity of this solution is O(n).

LeeCode: contains any duplicates in Java and JavaScript

Posted by in LeetCode on

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Soluton in JavaScript:

Solution in Java Using HashTable: