算法leetcode

【频数分桶】力扣1224-最大相等频率

字数统计: 1.5k字   |   阅读时长: 7分
, ,

摘要: 按频数分桶的系统设计

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个设计题，整体的算法框架是按频数分桶，而维护桶的数据结构用动态数组或链表都可以。

$1 题目

1224. 最大相等频率

给出一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回其长度：

从前缀中 删除一个 元素后，使得所剩下的每个数字的出现次数相同。

如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。

提示：

1
2
2 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

示例 1：
输入：nums = [2,2,1,1,5,3,3,5]
输出：7
解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4]=5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。

示例 2：
输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13

示例 3：
输入：nums = [1,1,1,2,2,2]
输出：5

示例 4：
输入：nums = [10,2,8,9,3,8,1,5,2,3,7,6]
输出：8

$2 题解

算法: 频数分桶

维护一个数据结构：

  • 插入 key，对应的频数加 1。
  • 查询当前有几种频数。
  • 查询每种频数对应几种 key。

维护桶结构，一个桶对应一种频数，所有 key 始终维护在其频数对应的桶中。

插入

插入时，通过哈希索引找到桶内 key 对应的节点，频数为 cnt，将节点从桶中删掉，插入到 cnt + 1 的桶中。

查询

查询(check)时，首先取得频数的种类数 c，如果 c > 2 则 check 不通过。如果 c = 1 或 c = 2，都是有可能 check 通过的。

  • c = 1，有一种频数，则先查具体频数 cnt
    • cnt 为 1，则 check 通过
    • cnt > 1，则看该频数下有多少 key，若只有一个，则 check 通过，否则不通过
  • c = 2，有两种频数，先查看具体频数，按照大小分别记为 min_cnt, max_cnt
    • min_cnt 为 1 且只有 1 个 key，check 通过
    • 有 max_cnt = min_cnt + 1 且 max_cnt 只有 1 个 key，check 通过
    • 其它情况 check 不通过

桶结构

桶结构可以用数组维护也可以用链表维护。

其它参考文章：

代码1 (链表维护桶)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
struct Bucket
{
    int val;
    list<int> keys;
    Bucket(int val):val(val)
    {
        keys = list<int>();
    }
};

struct Index
{
    list<Bucket>::iterator bucket_it;
    list<int>::iterator key_it;
    Index(list<Bucket>::iterator bucket_it, list<int>::iterator key_it):bucket_it(bucket_it),key_it(key_it){}
    Index(){}
};

class AllOne {
public:
    AllOne() {
        buckets = list<Bucket>();
        mapping = unordered_map<int, Index>();
    }

    void inc(int key) {
        if(mapping.count(key) == 0)
        {
            if(buckets.empty() || buckets.front().val > 1)
                buckets.emplace_front(1);
            buckets.front().keys.push_back(key);
            list<int>::iterator key_it = --buckets.front().keys.end();
            list<Bucket>::iterator bucket_it = buckets.begin();
            mapping[key] = Index(bucket_it, key_it);
        }
        else
        {
            Index idx = mapping[key];
            int val = idx.bucket_it -> val;
            auto nxt_bucket_it = next(idx.bucket_it, 1);
            if(nxt_bucket_it == buckets.end() || nxt_bucket_it -> val > val + 1)
            {
                nxt_bucket_it = buckets.insert(nxt_bucket_it, Bucket(val + 1));
            }
            (nxt_bucket_it -> keys).push_back(key);
            list<int>::iterator key_it = --(nxt_bucket_it -> keys).end();
            mapping[key] = Index(nxt_bucket_it, key_it);
            (idx.bucket_it -> keys).erase(idx.key_it);
            if((idx.bucket_it -> keys).empty())
            {
                buckets.erase(idx.bucket_it);
            }
        }
    }

    bool check()
    {
        int c = buckets.size();
        if(c > 2)
            return false;
        if(c == 1)
        {
            // 只有一种频数
            int cnt = buckets.begin() -> val;
            if(cnt == 1)
                return true;
            // cnt > 1
            return (buckets.begin() -> keys).size() == 1;
        }
        // c == 2
        auto it1 = buckets.begin();
        auto it2 = ++buckets.begin();
        int cnt1 = it1 -> val;
        int cnt2 = it2 -> val;
        if(cnt1 == 1 && (it1 -> keys).size() == 1)
            return true;
        if(cnt2 == 1 && (it2 -> keys).size() == 1)
            return true;
        if(cnt1 + 1 == cnt2 && (it2 -> keys).size() == 1)
            return true;
        if(cnt2 + 1 == cnt1 && (it1 -> keys).size() == 1)
            return true;
        return false;
    }

private:
    list<Bucket> buckets;
    unordered_map<int, Index> mapping;
};

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        AllOne allone;
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            allone.inc(nums[i]);
            if(allone.check())
                ans = i + 1;
        }
        return ans;
    }
};

代码2 (数组维护桶)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
        cnt_list.push_back({});
    }

    int get(int key) {
        auto it = mapping.find(key);
        if(it == mapping.end())
            return -1;
        int ans = (it -> second).first;
        list<PII>::iterator key_node = (it -> second).second;
        int cnt = key_node -> second;
        if((int)cnt_list.size() == cnt + 1)
            cnt_list.push_back({});
        list<PII> &new_key_list = cnt_list[cnt + 1];
        PII new_val = *key_node;
        ++new_val.second;
        cnt_list[cnt].erase(key_node);
        if(cnt_list[cnt].empty())
            active_bucket.erase(cnt);
        if(new_key_list.empty())
            active_bucket.insert(cnt + 1);
        new_key_list.insert(new_key_list.begin(), new_val);
        mapping[key].second = new_key_list.begin();
        return ans;
    }

    void put(int key, int value) {
        if(cap == 0) return;
        auto it = mapping.find(key);
        if(it != mapping.end())
        {
            mapping[key].first = value;
            get(key);
            return;
        }
        if(cnt_list.size() == 1)
            cnt_list.push_back({});
        if(cnt_list[1].empty())
            active_bucket.insert(1);
        cnt_list[1].insert(cnt_list[1].begin(), PII(key, 1));
        mapping[key] = PIL(value, cnt_list[1].begin());
    }

    bool check()
    {
        int c = active_bucket.size();
        if(c > 2)
            return false;
        if(c == 1)
        {
            int cnt = *active_bucket.begin();
            if(cnt == 1)
                return true;
            return cnt_list[cnt].size() == 1;
        }
        // c == 2
        vector<int> cnts(active_bucket.begin(), active_bucket.end());
        int min_cnt = min(cnts[0], cnts[1]);
        int max_cnt = max(cnts[0], cnts[1]);
        if(min_cnt == 1 && cnt_list[min_cnt].size() == 1)
            return true;
        if(max_cnt == min_cnt + 1 && cnt_list[max_cnt].size() == 1)
            return true;
        return false;
    }

private:
    using PII = pair<int, int>;
    using PIL = pair<int, list<PII>::iterator>;
    int cap;
    unordered_map<int, PIL> mapping;
    vector<list<PII>> cnt_list;
    unordered_set<int> active_bucket; // 有元素的桶
};

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        LFUCache lfu(5e4 + 1);
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            lfu.put(nums[i], 1);
            if(lfu.check())
                ans = i + 1;
        }
        return ans;
    }
};
Share