Move Zeroes

題目描述

給定一個陣列，將所有的0移動到右方，並保持陣列順序。不可以建立新的陣列。

解題思路

這題要運用的技巧類似於之前的Remove Duplicated in Sorted Array，運用Two Pointer解決。定義一個只有在條件不等於0的時候才跟隨著for loop增加的pointer。 Java的實作如下：

public void moveZero(int[] nums) {
    int p = 0;
    for(int i=0;i<nums.length;i++){
        if (nums[i] != 0) {
            nums[p] = nums[i];
            p+=1;
        }
    }

    while(p<nums.length){
        nums[p] = 0;
        p+=1;
    }
}

這題的精隨在於，要把移動位置與補上0拆成兩個功能。時間複雜度為O(n)，空間複雜度為O(1)

Intersection of Two Arrays II

題目描述

給定兩個陣列nums1與nums2，回傳兩個最大的子集合。

解題思路

Solution1

這題我第一個想到的方法是排序兩個陣列之後，使用兩個pointer去找出子集合，Java實現邏輯如下：

public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);

    List<Integer> result = new ArrayList<>();
    int i = 0, j = 0;

    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] > nums2[j]) {
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            result.add(nums1[i]); // 收集交集元素
            i++;
            j++;
        }
    }

    // 轉回 int[]
    return result.stream().mapToInt(Integer::intValue).toArray();
}

這麼做的時間複雜度為O(nlogn+mlogm)，原因是

Arrays.sort(nums1);  // O(n log n)
Arrays.sort(nums2);  // O(m log m)

while (i < nums1.length && j < nums2.length) {
    ...
    i++;  // 或
    j++;  // 或兩個都++
}
//i 和 j 只會往前走，絕對不會倒退
//i 最多走 n 步（nums1 走完就停）
//j 最多走 m 步（nums2 走完就停）
//所以 while 迴圈最多執行 n + m 次

//→ 雙指針掃描 = O(n + m)

空間複雜度則是O(min(n, m))，Java 的 Arrays.sort(int[]) 底層是 Dual-Pivot Quicksort，遞迴會用到 call stack： → O(log n) 但 log n 比 min(n, m) 小很多，可以忽略。

Solution2

第二種解法是利用HashMap紀錄nums1每個元素的出現次數，在for loop nums2比對。

public int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> countMap = new HashMap<>();

    // 統計 nums1 每個元素的頻率
    for (int num : nums1) {
        countMap.merge(num, 1, Integer::sum);
    }

    List<Integer> result = new ArrayList<>();

    // 遍歷 nums2，有對應到就加入結果並扣除次數
    for (int num : nums2) {
        int count = countMap.getOrDefault(num, 0);
        if (count > 0) {
            result.add(num);
            countMap.put(num, count - 1);
        }
    }

    return result.stream().mapToInt(Integer::intValue).toArray();
}

3Sum

題目描述

找出陣列中三個不相同的元素，加總等於0的所有組合。

解題思路

Solution 1

首先這題第一個想到的是暴力解，也就是三層for loop，找出等於0的組合之後，進行排序來確保元素沒有重複，之後加入陣列回傳。 實作程式碼如下：

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                for(int k=j+1;k<nums.length;k++){
                    if((nums[i]+nums[j]+nums[k]) == 0) {
                        List<Integer> temp = Arrays.asList(nums[i],nums[j],nums[k]);
                        temp.sort(Integer::compareTo);
                        if (!ret.contains(temp)) {
                            ret.add(temp);
                        }
                    }
                }
            }
        }
        return ret;
    }

時間複雜度O(n^^4)，空間複雜度O(n)

Solution 2

更好的做法是，使用Two Pointer解決，做法如下。

• 先排序陣列已縮小搜尋範圍。
• 找到未重複的i點之後，使用while處理two pointer，其中j等於i+1而k等於最大長度-1
• 判斷三者是否加總等於0，若大於0則k—，若小於0則j++，若是相同就加入陣列，並找出下一個不重複的j k值

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> returns = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            if(i>0 && nums[i] == nums[i-1]) continue;
            int j=i+1;
            int k=nums.length-1;
            while(j<k){
                int sum=nums[i]+nums[j]+nums[k];
                if(sum > 0) k--;
                if(sum < 0) j++;
                if(sum == 0) {
                    returns.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    j++;
                    k--;
                    while(j < nums.length-1 && nums[j] == nums[j-1]) j++;
                    while(k > j && nums[k] == nums[k+1]) k--;
                }
            }
        }
        return returns;
    }