代碼隨想錄第二天繼續(xù)數(shù)組相關(guān)題目

977. 有序數(shù)組的平方

一個按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

方法一

思路： 因為input數(shù)組已經(jīng)是 非遞減順序， 所以平方后的最大值可能出現(xiàn)在這個數(shù)組的兩側(cè)。所以可以利用兩個指針從input數(shù)組左右兩側(cè)開始取平方并比較，將其中較大的值放入output并移動指針，較小的停留在原地。如此從右向左依次填充output數(shù)組。

Time complexity: O(N)
Space complexity: O(1)

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int i = 0, j = n - 1, pos = n-1;
        while(i <= j){
            if( nums[i] * nums[i] >= nums[j] * nums[j] ){
                res[pos--] = nums[i] * nums[i];
                i++;  //left++
            } else{
                res[pos--] = nums[j] * nums[j];
                j--;   //right--
            }
        }
        return res;
    }
}

方法二
對各個元素平方后，利用Arrays.sort() function 對數(shù)組進行排序。
trivial

Arrays.sort() function 時間復(fù)雜度 O(nlogn)
空間復(fù)雜度 O(logn) 因為使用logn空間的棧進行排序

In Java 8, Arrays.sort(Object[]) is based on the TimSort algorithm, giving us a time complexity of O(n log(n)). In short, TimSort makes use of the Insertion sort and the MergeSort algorithms.
Arrays.sort(primitives) uses a Dual-Pivot Quicksort algorithm. Its internal implementation from the JDK 10 is typically faster than traditional one-pivot Quicksort. It offers O(n log(n)) average time complexity

209. 長度最小的子數(shù)組

Medium

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

1. 暴力求解
利用兩個 for 循環(huán)，一個 for 循環(huán)固定一個位置i，另一個 for 循環(huán)從 i 的下一個元素開始累加，當和大于等于 s 的時候終止內(nèi)層循環(huán)，順便記錄下最小長度

時間復(fù)雜度 O(n*n)
空間復(fù)雜度：O(1)
提交超時

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        //因為要用來比較哪個值更小，所以初始為int Max_VALUE
        int res = Integer.MAX_VALUE ; 
        for(int i = 0; i < nums.length; i++){
            sum = nums[i];
            if(sum >= target) return 1;
            
            for(int j = i + 1; j < nums.length; j++){
                sum += nums[j];
                if(sum >= target){
                    res = Math.min(res, j - i + 1);
                    break; //因為要找符合條件最短的子序列，所以一旦符合條件就break
                }
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res ;
    }
}

2. 滑動窗口

所謂滑動窗口，就是不斷的調(diào)節(jié)子序列的起始位置和終止位置，從而得出我們要想的結(jié)果。

在暴力解法中，是一個for循環(huán)滑動窗口的起始位置，一個for循環(huán)為滑動窗口的終止位置，用兩個for循環(huán) 完成了一個不斷搜索區(qū)間的過程.

滑動窗口則通過雙指針分別指向起始位置與終止位置，通過一個for循環(huán)來完成

在本題中實現(xiàn)滑動窗口，主要確定如下三點：

• 窗口內(nèi)是什么？
• 如何移動窗口的起始位置？
• 如何移動窗口的結(jié)束位置？

窗口就是 滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組。

窗口的起始位置如何移動：如果當前窗口的值大于s了，窗口就要向前移動了（也就是該縮小了）。

窗口的結(jié)束位置如何移動：窗口的結(jié)束位置就是遍歷數(shù)組的指針，也就是for循環(huán)里的索引。

解題的關(guān)鍵在于 窗口的起始位置如何移動，如圖所示：

在當前終止位置固定時， 找到滿足sum >= target 的最短窗口。 然后再處理下一個終止位置

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0, left = 0; // sum為當前窗口數(shù)值之和； left為當前起始位置
        int res = Integer.MAX_VALUE ;
        for(int right = 0; right < nums.length; right++){ //right當前終止位置
            sum += nums[right];
            while(sum >= target){
                sum -= nums[left];
                res = Math.min(res, right - left + 1);
                left++; //變更窗口起始位置
            }
            
        }
        return res == Integer.MAX_VALUE ? 0 : res ;
    }
}

時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

為什么時間復(fù)雜度是O(n)。

不要以為for里放一個while就以為是O(n^2)， 主要是看每一個元素被操作的次數(shù)，每個元素在滑動窗后進來操作一次，出去操作一次，每個元素都是被操作兩次，所以時間復(fù)雜度是 2 × n 也就是O(n)。

59. 螺旋矩陣II

Medium難度

給定一個正整數(shù) n，生成一個包含 1 到 n^2 所有元素，且元素按順時針順序螺旋排列的正方形矩陣。

示例:

輸入: 3 輸出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

spiraln.jpg

思路：
結(jié)果為 n * n 矩陣，模擬從1 到 n*n 螺旋狀填充這個矩陣的過程

填充過程從左上角[1,1]開始,總是*順序遵循以下四個方向：

1. 自左向右填充當前最上行；
2. 自上向下填充當前最右列；
3. 從右向左填充當前最下行；
4. 自下向上填充當前最左列；

可以定義四個變量來表示當前上，下，左，右 四個邊界，每完成一個方向，更新相應(yīng)的邊界值。 例如從左到右填完后，上邊界 top += 1，相當于上邊界向內(nèi)縮 1

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        //定義當前左右上下邊界
        int left = 0;
        int right = n - 1;
        int top = 0;
        int buttom = n - 1;
        int curr = 1;    //填充起始值
        int tar = n * n; //填充終止值， 也是需要填充的個數(shù)
        
        while(curr <= tar){
           //1.自左向右
           for(int i = left; i <= right; i++){
               res[top][i] = curr++; //先賦值，再increment
           }
            top++;  //最上行處理完畢，top邊界下移
            
            //2.自上向下
            for(int i = top; i <= buttom; i++){
                res[i][right] = curr++;
            }
            right--; //最右列處理完畢，right邊界左移
            
            //3. 從右向左
            for(int i = right; i >= left; i--){
               res[buttom][i] = curr++; 
            }
            buttom--; //最下行處理完畢，buttom邊界上移
            
            //4. 自下向上
            for(int i = buttom; i >= top; i--){
                res[i][left] = curr++;
            }
            left++; //最左列處理完畢，left邊界右移
            
        }
        
        return res;
    }
}

時間復(fù)雜度：O(n* n)
空間復(fù)雜度：O(n* n)