算法小技巧

for 循环里套 for 循环时间复杂度会爆表，呈指数式增长，宁愿预处理也不要这样。

其中，在获取整个数组的最大的三个数的过程中，我想到一种非常简便的数据结构：保持顺序和长度，添加到其中的数会自动保持顺序，同时把多余的数据挤出。核心在于，添加的时候，先从最末尾的数据进行对比，能加入就替换，不能加入就算了，然后比较最后一项和倒数第二项，如果满足顺序就保持，不满足就交换，直到数组的最前端，这个数据结构的好处是长度固定，保持顺序，但是添加的时候很麻烦，时间复杂度是 O(n)。所以这个数据结构不适用于太多的元素。

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


//max1 > max2 > max3
int max1 = Integer.MIN_VALUE,max2 = Integer.MIN_VALUE,max3 = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
    int ele = nums[i];
    if (ele > max3) {
        max3 = ele;
    }
    if (max3 > max2) {
        int buffer = max2;
        max2 = max3;
        max3 = buffer;
    }
    if (max2 > max1) {
        int buffer = max1;
        max1 = max2;
        max2 = buffer;
    }
}

HashMap 的 get 方法的算法复杂度为 O(1)，当然这是理想情况，但是这也说明了，hashMap 在查找的时候的算法复杂度是 O(1)。这是链表的数据结构的优势