1. 插入的时候，把插入点的元素放到数组最后，然后把插入点的元素进行替换
2. 删除的时候，假删除，然后等数组容量超过一定阀值一起删除

LRU

• FIFO

• LFU

• LRU

• 0004: Median of Two Sorted Arrays

归并排序，先统计两个数组的数量，计算出中位数的位置，然后归并排序，找到对应的数字并计算，这个方法简单但是复杂度是O(mn)，复杂度不符号要求。这里使用求第k个数的思路。分别对二个数组进行k/2的查找，然后比较，淘汰掉不符号要求的k/2，然后继续查找。

fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {

    let mut left = (nums1.len() + nums2.len() + 1) / 2;
    let mut right = (nums1.len() + nums2.len() + 2) / 2;
	  // 考虑到奇数和偶数的情况
    let l = get_kth(&nums1, 0, nums1.len() - 1, &nums2, 0, nums2.len() - 1, left);
    let r = get_kth(&nums1, 0, nums1.len() - 1, &nums2, 0, nums2.len() - 1, right);

    return (l + r) as f64 / 2.0
}

fn get_kth(nums1: &[i32], start1: usize, end1: usize, 
					 nums2: &[i32], start2: usize, end2: usize, k: usize) -> i32 {

    let len1 = end1 - start1 + 1;
    let len2 = end2 - start2 + 1;

    // 让len1的长度小于len2，这样保证在数组为空的时候，一定是len1?
    if len1 > len2 {
        return get_kth(nums2, start2, end2, nums1, start1, end1, k)
    }

    if len1 == 0 {
        return nums2[start2 + k - 1];
    }

    if k == 1 {
        return min(nums1[start1], nums2[start2]);
    }

    let i = start1 + min(len1, k / 2) - 1;
    let j = start2 + min(len2, k / 2) - 1;

    if nums1[i] > nums2[j] {
        return get_kth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
    }
    
    return get_kth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}

• 0011: Container With Most Water

核心思路: 是头尾两个指针，对向遍历，短的一侧需要前进，因为容积的大小取决小短的一侧，短的一侧不动的话，另外一侧无论怎么懂都不为比当前的容积大。因为高度固定了，宽度是目前最大的。所以短的一侧需要前移去寻找下一个最大的容积。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                max(res, (j - i) * height[i++]): 
                max(res, (j - i) * height[j--]); 
        }
        return res;
    }
};

• 0015: 3Sum