How to Find the Longest Harmonious Subsequence?

  • 时间：2020-09-18 17:01:02
  • 分类：网络文摘
  • 阅读：107 次

We define a harmounious array as an array where the difference between its maximum value and its minimum value is exactly 1. Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

Bruteforce All Subsequences

One solution is to bruteforce all the subsequences, which is exponential. The total subsequences is C(n, 1) + C(n, 2) + C(n, 3) + … C(n, n). We can use two nested loops, the outer loop is from 0 to (2^n)-1 where n is the size of the array, and the inner loop is from 0 to n-1.

By generating all the subsequences, we can increment the counter once we find the Harmonious subsequence where the min and max value is exactly one difference.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int findLHS(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < (1 << nums.size()); ++ i) {
            int count = 0, minv = INT_MAX, maxv = INT_MIN;
            for (int j = 0; j < nums.size(); ++ j) {
                if ((i & (1 << j)) != 0) {
                    minv = min(minv, nums[j]);
                    maxv = max(maxv, nums[j]);
                    count ++;
                }
            }
            if ((minv != INT_MAX) && (maxv == minv + 1)) {
                ans = max(ans, count);
            }
        }        
        return ans;
    }
};
class Solution {
public:
    int findLHS(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < (1 << nums.size()); ++ i) {
            int count = 0, minv = INT_MAX, maxv = INT_MIN;
            for (int j = 0; j < nums.size(); ++ j) {
                if ((i & (1 << j)) != 0) {
                    minv = min(minv, nums[j]);
                    maxv = max(maxv, nums[j]);
                    count ++;
                }
            }
            if ((minv != INT_MAX) && (maxv == minv + 1)) {
                ans = max(ans, count);
            }
        }        
        return ans;
    }
};

Apparently, this bruteforce is extremely inefficient.

Using a Hashmap

We can do one-pass scan to count the occurences for each number in a hash map. Then, by going through the numbers in the hash map, then the Harmonious subsequence can be checked if the next number is in the hash map – the length will be the sum of the counters for both numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int findLHS(vector<int>& nums) {        
        unordered_map<int, int> count;
        for (const auto &n: nums) {
            count[n] ++;
        }
        int ans = 0;
        for (auto it = begin(count); it != end(count); ++ it) {
            int next = it->first + 1;
            if (count.find(next) != count.end()) {
                ans = max(ans, it->second + count[next]);
            }
        }
        return ans;
    }
};
class Solution {
public:
    int findLHS(vector<int>& nums) {        
        unordered_map<int, int> count;
        for (const auto &n: nums) {
            count[n] ++;
        }
        int ans = 0;
        for (auto it = begin(count); it != end(count); ++ it) {
            int next = it->first + 1;
            if (count.find(next) != count.end()) {
                ans = max(ans, it->second + count[next]);
            }
        }
        return ans;
    }
};

We can also do this one-pass, by checking the previous and next number in the hash map as we going through each number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int findLHS(vector<int>& nums) {
        int ans = 0;
        unordered_map<int, int> data;
        for (const auto &n: nums) {
            data[n] ++;
            if (data.find(n + 1) != data.end()) {
                ans = max(ans, data[n] + data[n + 1]);
            }
            if (data.find(n - 1) != data.end()) {
                ans = max(ans, data[n] + data[n - 1]);
            }
        }        
        return ans;
    }
};
class Solution {
public:
    int findLHS(vector<int>& nums) {
        int ans = 0;
        unordered_map<int, int> data;
        for (const auto &n: nums) {
            data[n] ++;
            if (data.find(n + 1) != data.end()) {
                ans = max(ans, data[n] + data[n + 1]);
            }
            if (data.find(n - 1) != data.end()) {
                ans = max(ans, data[n] + data[n - 1]);
            }
        }        
        return ans;
    }
};

Both approaches are using hash map, thus O(N) space and O(N) time complexity.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
雅培配方奶粉被曝不符合安全标准　 营养和安全：有机食品PK常规食品　 蔬菜如何烹制，营养、健康又安全　 八种简易食疗方，巧防春季流感　 春季养生：喝花茶可护肝，预防感冒　 农夫山泉被质疑标准不及自来水　 北京工商局4月10日食品安全信息　 保健养生：果蔬是“抗癌”食品首选　 国家食药总局曝光10种假冒保健食品　 饮食养生：春韭对人体有何保健作用　
评论列表
添加评论