【java容器的刻意练习】【五】ArrayList考点

2020-02-03 本文已影响0人程序猿修仙传

一般ArrayList面试考点都在考察应聘者是否知道ArrayList底层是数组，优缺点，各种操作的时间复杂度，最后是跟其他容器的区别。

而笔试单独考察比较少，会借着数组的特定排序，考察应聘者是否会充分利用数组的优点。

我们来看看leetcode的第905题按奇偶排序数组：

//给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。 
//
// 你可以返回满足此条件的任何数组作为答案。 
//
// 
//
// 示例： 
//
// 输入：[3,1,2,4]
//输出：[2,4,3,1]
//输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= A.length <= 5000 
// 0 <= A[i] <= 5000 
// 
// Related Topics 数组


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] sortArrayByParity(int[] A) {
        
    }
}
//leetcode submit region end(Prohibit modification and deletion)

如果我们不考虑数组的优缺点，不考虑性能，不考虑空间，这样做最简单：

新建一个跟A长度一样的数组res
遍历2遍数组A，第一遍把偶数都插入res，第二遍把奇数都插入到res
最后返回res

但是，我们在上一篇学过，数组最擅长是按索引随机访问，时间复杂度都是O(1)的。如果能把前面的奇数与后面的偶数交换，不就可以节省空间和时间吗？

那么，我们再仔细读读这句话：

把前面的奇数与后面的偶数交换

那我们可以同时准备2个索引，一个从前往后，另一个从后往前，同时遍历数组，当前面发现奇数就停下来，当后面发现偶数也停下来，然后2个数交换，继续，一直到2个索引相等，不就完成了吗？

好，下面我们整理下思路：

准备2个索引
同时遍历数组，一个从前往后，另一个从后往前
当前面索引发现奇数就停下来
当后面索引发现偶数也停下来
前后两数交换
2个索引相等时候退出

class Solution {
    public int[] sortArrayByParity(int[] A) {

        // 准备2个索引
        int left = 0;
        int right = A.length - 1;

        // 同时遍历数组，2个索引相等时候退出
        while (left < right) {

            // 一个索引从左往右，当左索引发现奇数就停下来
            while (A[left] % 2 == 0 && left < right) {
                left++;
            }

            // 一个索引从右往左，当右索引发现偶数也停下来
            while (A[right] % 2 > 0 && left < right) {
                right--;
            }

            // 前后两数交换
            if (left < right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
            }
        }

        return A;
    }

}

提交下，通过了，各方面都还不错。

Runtime: 1 ms, faster than 99.97% of Java online submissions for Sort Array By Parity.
Memory Usage: 41.4 MB, less than 77.78% of Java online submissions for Sort Array By Parity.

当然，不仅仅是左右索引，用奇偶索引一起从左边开始也是可以的。我们就不再用代码详述了。

所以，一般遇到数组排序，都是考虑充分利用数组索引访问O(1)的特性，进行解题，这样一般解出来的题目性能都不会差。

我们再来看一题118. 杨辉三角，还是用到ArrayList的通过索引访问是最快的，这样一个特性，来降低代码复杂度。

//给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。 
//
// 
//
// 在杨辉三角中，每个数是它左上方和右上方的数的和。 
//
// 示例: 
//
// 输入: 5
//输出:
//[
//     [1],
//    [1,1],
//   [1,2,1],
//  [1,3,3,1],
// [1,4,6,4,1]
//] 
// Related Topics 数组

我们先观察下，每一行是一个数组。每个数组第一个数值是1。以后每个索引j对应的数值，就是上一个数组的索引j-1的数值，加上索引j的数值。

很绕口对吧，假设第一个数组是A，第二个数组是B，那么：

B[ j ] = A[ j-1 ] + A[ j ]

所以代码如下：

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> generate(int numRows) {

        // 先准备一个数组
        List<Integer> arrayList = new ArrayList<>();
        // 保存返回的结果
        List<List<Integer>> listListRet = new ArrayList<List<Integer>>();

        // 用户输入多少行，就生成多少数组
        for (int i = 0; i < numRows; i++) {

            // 每个数组第一个数固定是1
            arrayList.add(0, 1);

            // 每个数组第二个数开始，都根据规律计算即可
            for (int j = 1; j < i; j++) {
                // 这里的 j 是上一个数组的索引，所以计算下一个数组数值就是 B[j] = A[j] + A[j+1]
                arrayList.set(j, arrayList.get(j) + arrayList.get(j+1));
            }
            //System.out.println(arrayList.toString());

            // 保存每一行生成的结果
            listListRet.add(new ArrayList<Integer>(arrayList));
        }

        //System.out.println(listListRet.toString());

        return listListRet;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

提交看看结果，看来还不错。

执行结果：通过显示详情
执行用时 :1 ms, 在所有 Java 提交中击败了99.05%的用户
内存消耗 :33.7 MB, 在所有 Java 提交中击败了90.02%的用户

【java容器的刻意练习】【五】ArrayList考点

猜你喜欢

热点阅读