基于数组设计的LRUCache

• 优势
  • 支持泛型
  • 空间更少

代码

import java.util.*;

class LruCache<K, V> {
    private int capacity;

    private int size;
    private K[] keys;
    private V[] values;
    private V nullValue;

    public LruCache(int capacity, V nullValue) {
        this.capacity = capacity;
        this.size = 0;
        keys = (K[]) new Object[capacity];
        values = (V[]) new Object[capacity];
        this.nullValue = nullValue;
    }

    V get(K k) {
        int index = exist(k);
        if (index > -1) {
            emerge(index);
            return values[size - 1];
        }
        return nullValue;
    }

    int exist(K k) {
        for (int i = 0; i < size; i++) {
            if (keys[i].equals(k)) {
                return i;

            }
        }
        return -1;
    }

    void set(K k, V v) {
        //上浮
        int index = exist(k);
        if (index > -1) {
            keys[index] = k;
            values[index] = v;
            emerge(index);
        } else {
            if (size < capacity) {
                keys[size] = k;
                values[size] = v;
                size = size + 1 >= capacity ? capacity : size + 1;
            } else {
                emerge(0);
                keys[size - 1] = k;
                values[size - 1] = v;
            }
        }
    }

    void emerge(int index) {
        assert index>=0:"index 要大于等于0";
        V tempValue = values[index];
        K tempKey = keys[index];
        for (int i = index + 1; i < size ; i++) {
            keys[i - 1] = keys[i];
            values[i - 1] = values[i];
        }
        keys[size - 1] = tempKey;
        values[size - 1] = tempValue;
    }
}

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
 public int[] LRU(int[][] operators, int k) {
        LruCache<Integer, Integer> lruCache = new LruCache<>(k, -1);
        int size = 0;
        for (int i = 0; i < operators.length; i++) {
            if (operators[i][0] == 2) {
                size++;
            }
        }
        int[] result = new int[size];
        int index = 0;
        for (int i = 0; i < operators.length; i++) {
            if (operators[i][0] == 1) {
                lruCache.set(operators[i][1], operators[i][2]);
            }
            if (operators[i][0] == 2) {
                result[index++] = lruCache.get(operators[i][1]);
            }
        }
        return result;
        // write code here
    }
}