runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: None

Plus One

📖 description

給定一個數值陣列表示一個數字，請求將這個數字 +1 (可能進位)。

ex.
    Input: 
        digits = [9]

    Output: [1,0]

    Explanation: 
        The array represents the integer 9.
        Incrementing by one gives 9 + 1 = 10.
        Thus, the result should be [1,0].

🧠 solution

可以直接在陣列尾 +1 後再處理每個位數的進位問題，如果最高位有進位再新建陣列來處理。
但其實可以利用一些方法來加速，比如如果當前位數不是 9 ，就代表不會發生進位，此時可以直接回傳，而如果最高位有發生進位，由於先前已經做過處理，其實只需要將當前陣列的最高位改成 1 ，並新增 0 再最後即可，因為如果有發生進位，最低位一定是 0 。

⏳ time complexity

遍歷一次陣列，時間複雜度 O(n) 。
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size()-1;
        for(int i=n;i>=0;--i){
            if(digits[i]==9){   // 當前位數為 9 
                digits[i]=0;
            }
            else{
                ++digits[i];    // 沒有發生進位，直接回傳
                return digits;
            }
        }
        digits.emplace_back(0); // 發生進位後最低位一定為 0
        digits[0] = 1;          // 最高位一定為 1 
        return digits;
    }
};