C# solution


  • 0
    D

    '''public class LFUCache
    {
    public int capacity;
    Dictionary<int, int> data = new Dictionary<int, int>();
    Dictionary<int, List<int>> countArray = new Dictionary<int, List<int>>();
    Dictionary<int, int> count = new Dictionary<int, int>();
    public int minCount = 1;
    public LFUCache(int capacity)
    {
    this.capacity = capacity;
    }

        public int get(int key)
        {
            if (capacity == 0)
                return -1;
            if (data.ContainsKey(key))
            {
                var countTimes = count[key];
                count[key]++;
                var arr = countArray[countTimes];
                arr.Remove(key);
                if (countArray.ContainsKey(++countTimes))
                {
                    arr = countArray[countTimes];
                    arr.Add(key);
                }
                else
                {
                    countArray.Add(countTimes, new List<int>() { key });
                }
    
                return data[key];
    
            }
            return -1;
        }
    
        public void put(int key, int value)
        {
            if (data.ContainsKey(key))
            {
                data[key] = value;
                var countTimes = count[key];
                count[key]++;
                var arr = countArray[countTimes];
                arr.Remove(key);
                if (countArray.ContainsKey(++countTimes))
                {
                    arr = countArray[countTimes];
                    arr.Add(key);
                }
                else
                {
                    countArray.Add(countTimes, new List<int>() { key });
                }
            }
            else
            {
                if (data.Count >= capacity)
                {
                    while (minCount < 10000000)
                    {
                        if (countArray.ContainsKey(minCount)&& countArray[minCount].Count>0)
                        {
                            count.Remove(countArray[minCount][0]);
                            data.Remove(countArray[minCount][0]);
                            countArray[minCount].RemoveAt(0);
                            if (countArray[minCount].Count == 0)
                                countArray.Remove(minCount);
                        
                            break;
                        }
                        else
                            minCount++;
                    }
                }
                data.Add(key, value);
                count.Add(key, 1);
                if (countArray.ContainsKey(1))
                {
                    countArray[1].Add(key);
    
                }
                else
                {
                    countArray.Add(1, new List<int>() { key });
                }
                minCount = 1;
    
    
            }
    
    
        }
    }'''
    

    use three hashmap to solve this problem


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.