1. 陣列的改變和移動總結

1.1 陣列的改變

陣列在記憶體中是一塊連續的記憶體空間，我們可以直接通過下標進行訪問，并進行修改，

在Java中，對于List型別來說，我們可以通過set(idx, element)方法將idx位置的元素進行修改，

1.2 陣列的移動

陣列的移動不能通過一條陳述句來實作，通常來說需要通過：插入、洗掉或者多次交換來實作，

1.3 陣列的插入

陣列的插入比較麻煩，我們想要在下標為k的位置插入一個元素時，首先需要將k及以后的元素往后移動一個位置，然后再將元素插入到k的位置處，

在Java中，對于List型別來說，我們可以通過add(idx, element)方法將元素添加到idx下標處，

1.4 陣列的洗掉

洗掉下標為k的元素時，需要將k以后的元素向前移動一個位置，

對于List型別來說，我們可以通過remove(idx)方法洗掉下標為idx的元素，

2. 題目記錄

453. ?最小操作次數使陣列元素相等

分析題意

給你一個長度為 n的整數陣列，每次操作將會使 n - 1 個元素增加 1 ，回傳讓陣列所有元素相等的最小操作次數，

思路分析

這道題有一個很巧妙的思路：由于我們并不關心最終元素相等時的值而只關心操作的次數，所以我們可以將上述問題轉化為：每次操作使一個元素減少1，回傳讓陣列中所有元素相等的最小運算元，這樣就簡單了：我們想要運算元最小，就必須找到能使所有元素相等的最小值，其實這個值就是陣列中的最小值，而操作的次數就是：每個數與最小值的差值之和，

class Solution {
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE;

        for(int i = 0; i < nums.length; i++){
            min = Math.min(nums[i], min);
        }

        int ans = 0;
        for(int i = 0; i < nums.length; i++){
            ans = ans + nums[i] - min;
        }

        return ans;

    }
}

那么正向思考這個問題應該怎么做呢？

注意到：每次操作都使n-1個數加1，也就是所每次操作都會使該陣列的sum加上n-1，假設最小運算元為a次，那么此時一定有數學關系式：\(a(n-1) + sum = nx\)，其中x為最終陣列中的值，

僅有這一個關系式的約束是不夠的，我們還要想清楚的一點就是：原陣列中最小的那個數需要操作a次才能夠變為x ，即：\(min + a = x\) (這個比較難想明白)

根據這兩個公式我們就可以求出最終的a了：\(a = sum - n * min\)

class Solution {
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE;
        int sum = 0;

        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            min = Math.min(nums[i], min);
        }
        return sum - nums.length * min;

    }
}

復雜度分析

時間復雜度：O(n)

空間復雜度：O(1)

665. 非遞減數列

分析題意

給你一個長度為 n 的整數陣列 nums，請你判斷在最多改變 1 個元素的情況下，該陣列能否變成一個非遞減數列，

思路分析

從前往后遍歷，找到第一個 a > b的情況時，對a 或 b 的值進行修改，然后判斷修改后的陣列是否為非遞減陣列即可，關鍵在于：修改 a 還是 修改 b 呢？

這里其實是有兩個選擇的：

1. 對于 [1, 3, 4, 2, 5] ，此時應該修改 b；
2. 對于[1, 3, 4, 3, 4], 此時應該修改 a；

一種簡單的方法就是：我們兩種情況都嘗試，看看是否能夠得到非遞減陣列，

class Solution {
    public boolean checkPossibility(int[] nums) {

        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i] > nums[i + 1]){
                int n_1 = nums[i];
                int n_2 = nums[i + 1];

                // 修改a
                nums[i] = n_2;
                if(checkMethod(nums)) return true;

                // 復位a
                nums[i] = n_1;
                // 修改b
                nums[i + 1] = n_1;
                if(checkMethod(nums)) return true;

                return false;
            }
        }
        return true;
    }

    boolean checkMethod(int[] nums){
        for(int i = 1; i < nums.length; i++){
            if(nums[i - 1] > nums[i]) return false;
        }

        return true;
    }
}

復雜度分析

時間復雜度：O(n)

空間復雜度：O(1)

283. 移動零

分析題意

給定一個陣列 nums，撰寫一個函式將所有 0 移動到陣列的末尾，同時保持非零元素的相對順序，

請注意 ，必須在不復制陣列的情況下原地對陣列進行操作，

關鍵點：保持非零元素的相對順序，

思路分析

首先排除首尾雙指標的思路，因為要保持非零元素的相對順序，所以不能夠使用首尾雙指標來做，

首尾雙指標是指：左指標找第一個0元素，右指標找第一個非0元素，然后交換兩個元素，有點像歸并排序，

由于不復制陣列，所以大概率還是使用雙指標來操作，分析一下，假設我們知道left左側都是非零元素，然后在left右側找到了一個非零元素，此時只需要將該元素放在left下標下即可，

基于此思路，我們用left來標識已經處理元素的右邊界，然后通過右指標去尋找下一個非0元素，找到后放置在left位置并將left指標右移，

class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        int right = 0;

        while(right < nums.length){
            if(nums[right] != 0){
                nums[left] = nums[right];
                left ++;
            }

            right ++;
        }

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

    }
}

復雜度分析

時間復雜度：O(n)

空間復雜度：O(1)

本文來自博客園，作者：睡覺不打呼，轉載請注明原文鏈接：https://www.cnblogs.com/404er/p/array_move.html

標籤：其他

上一篇：leetcode 669. Trim a Binary Search Tree 修剪二叉搜索樹 (簡單)

下一篇：「浙江理工大學ACM入隊200題系列」問題 E: 零基礎學C/C++78——求奇數的乘積