考點：遍歷、查找、排序、時空效率、思維、排序演算法

// Q01 二維部分有序陣列查找【善用性質】
// Q06 旋轉陣列中的最小元素【二分 || 暴力】
Q13 調整陣列順序使奇數位于偶數前
/ Q19 順時針列印矩陣【使用邊界變數】
/ Q28 找出陣列中出現超過一半的數字
- 方法 1：HashMap統計各數字出現次數
- 方法 2：基于Partition查找第K大 O(n)
- 方法 3：遍歷判斷，兩兩相消
/ Q30 連續子陣列的最大和【dp ，Math.max()】
/ Q32 把陣列排成最小的數【Collections.sort()，Integer.toString(int n)，stringBuilder.append(str)】
/// Q35 陣列中的逆序對
- 方法 1：歸并排序統計逆序對
- 方法 2：樹狀陣列
/ Q37 數字在排序陣列中出現的次數【二分查找寫法分析，equal_range()】
- 方法 1：手寫二分查找，搜索 k-0.5和 k+0.5
- 方法 2：C++ STL equal_range()
// Q40 找出陣列中兩個只出現一次的數字【位運算】
- 拓展：陣列a中只有一個數出現一次，其他數字都出現了3次，找出這個數字
/ Q50 陣列中重復的數字【不借助輔存】
Q51 構建乘積陣列

// Q01 二維部分有序陣列查找【善用性質】

在一個二維陣列中（每個一維陣列的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，請完成一個函式，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數，

由于矩陣部分有序，向上數字遞減，向右數字遞增：

目標數字只會出現在行首小于該數的行中
遍歷行i ，若列j 對應的元素大于目標，那么在前 i-1 行，目標只會出現在 j列及以后，

因此，可以從左下角開始查找，目標比左下角數字小時，上移；當要目標比左下角數字大時，右移，
搜索的路線是階梯狀，復雜度為O(行數+列數)，

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int nrows = array.size();
        int ncols = array[0].size();
         
        int i = nrows - 1, j = 0;
         
        while(i >= 0 && j < ncols){
            if(array[i][j] == target) return true;
            else if(array[i][j]< target ){
                j++;
            }else i--;
        }
         
        return false;
    }
};

WA警告:

之前的錯誤代碼版本如下，由于判斷條件中的 && 寫成 , 造成段錯誤（陣列越界訪問）：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int nrows = array.size();
        int ncols = array[0].size();
        if( ncols == 0 || nrows == 0) return false;
        for(int i = nrows - 1, j = 0; i >= 0, j < ncols; i--){
            if( array[i][j] == target )
                return true;
            if( array[i][j] < target){
                i++;
                j++;
            }
        }
          
        return false;
    }
};

// Q06 旋轉陣列中的最小元素【二分 || 暴力】

把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，
輸入一個非遞減排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，
例如陣列{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該陣列的最小值為1，
NOTE：給出的所有元素都大于0，若陣列大小為0，請回傳0，

由于旋轉后，陣列前半段非減，后半段非減，所以從后往前遍歷，轉折點一定是最小元素，如果沒有轉折點，那么所有元素都相等，
? . .··
? . ·``

但是這個轉折點可以試著二分，由于轉折處的右側是最小元素，所以選擇盡量讓區間右端點落在最小元素上，那么：

array[mid] > array[high]
出現這種情況的array類似[3,4,5,6,0,1,2]，此時最小數字一定在mid的右邊，
low = mid + 1
array[mid] == array[high]:
出現這種情況的array類似 [1,0,1,1,1] 或者[1,1,1,0,1]，此時最小數字不好判斷在mid左邊還是右邊,這時只好一步步縮小區間，
high = high - 1
array[mid] < array[high]:
出現這種情況的array類似[2,2,3,4,5,6,6],此時最小數字一定就是array[mid]或者在mid的左邊，因為右邊必然都是遞增的，
high = mid

注意，考慮最后區間長為2或為3 的情況，上述的收斂方式都會使得 low 和 high 最終都指向最小元素，

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0)
            return 0;
        int lo =0, hi = rotateArray.size()-1,mid;
         
        while(lo< hi){
            mid = lo+((hi-lo)>>1);
            if(rotateArray[mid]>rotateArray[hi])
                lo=mid+1;
            else if (rotateArray[mid] == rotateArray[hi])
                hi-=1;
            else hi=mid;
        }
        return rotateArray[hi];
    }
};

Q13 調整陣列順序使奇數位于偶數前

輸入一個整數陣列，實作一個函式來調整該陣列中數字的順序，使得所有的奇數位于陣列的前半部分，所有的偶數位于陣列的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變，

方法1：新開陣列，先添加奇數，再添加偶數，代碼略，

方法2：不借助額外記憶體

/**
 * 1.要想保證原有次序，則只能順次移動或相鄰交換，
 * 2.i從左向右遍歷，找到第一個偶數，
 * 3.j從i+1開始向后找，直到找到第一個奇數，
 * 4.將[i,...,j-1]的元素整體后移一位，最后將找到的奇數放入i位置，然后i++，
 * 5.終止條件：j向後遍歷查找失敗，
 */
public void reOrderArray2(int [] a) {
    if(a==null||a.length==0)
        return;
    int i = 0,j;
    while(i<a.length){
        while(i<a.length&&!isEven(a[i]))
            i++;
        j = i+1;
        while(j<a.length&&isEven(a[j]))
            j++;
        if(j<a.length){
            int tmp = a[j];
            for (int j2 = j-1; j2 >=i; j2--) {
                a[j2+1] = a[j2];
            }
            a[i++] = tmp;
        }else{// 查找失敗
            break;
        }
    }
}
boolean isEven(int n){
    if(n%2==0)
        return true;
    return false;
}

/ Q19 順時針列印矩陣【使用邊界變數】

輸入一個矩陣，按照從外向里以順時針的順序依次列印出每一個數字，例如，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 則依次列印出數字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

/**
 A--------------------------------------------------------
 * 思路1：vis陣列記錄 - 簡單但浪費空間
 * 思路2：用變數記錄當前是第幾圈 - 邊界計算有點麻煩
 * 思路☆：用四個變數分別記錄當前的四周邊界，檢查是否在邊界內 && 邊界是否滿足條件
 T--------------------------------------------------------
 * 注意邊界的檢查（保證[在邊界內 && 邊界合法]） 
 */

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> ans = new ArrayList<>();

        if(matrix.length == 0 || matrix[0].length == 0)
            return ans;

        int nrow = matrix.length, ncol = matrix[0].length;
        int top=0,left=0,bottom=nrow-1,right=ncol-1;
        while (top<=bottom&&left<=right){
            // top: left -> right
            for(int i=left;i<=right;i++){
                ans.add(matrix[top][i]);
            }top++;
            // right: top -> bottom
            for(int i=top;i<=bottom&&left<=right;i++){//其實這里left<=right的判斷多余，因為left和right的值都還沒有變化
                ans.add(matrix[i][right]);
            }right--;
            // bottom: right -> left
            for(int i=right;i>=left&&top<=bottom;i--){
                ans.add(matrix[bottom][i]);
            }bottom--;
            // left: bottom -> top
            for(int i=bottom;i>=top&& left<=right;i--){
                ans.add(matrix[i][left]);
            }left++;
        }
        return ans;
    }
}

/ Q28 找出陣列中出現超過一半的數字

陣列中有一個數字出現的次數超過陣列長度的一半，請找出這個數字，例如輸入一個長度為9的陣列{1,2,3,2,2,2,5,4,2}，由于數字2在陣列中出現了5次，超過陣列長度的一半，因此輸出2，如果不存在則輸出0，

方法 1：HashMap統計各數字出現次數

/**
 * 用 HashMap 統計各個數字出現的次數
 * 注意 HashMap 的使用方法
 */

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Solution {
    public int  MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<array.length;i++){
            if(!map.containsKey(array[i])){
                map.put(array[i],1);
            }else{
                int cnt = map.get(array[i]);
                map.put(array[i],++cnt);
            }
        }

        Iterator iter = map.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry entry = (Map.Entry)iter.next();
            Integer key = (Integer)entry.getKey();
            Integer val = (Integer)entry.getValue();
            if(val>array.length/2){
                return key;
            }
        }
        return 0;
    }
}

方法 2：基于Partition查找第K大 O(n)

? 對于該陣列，若存在出現次數超過一半的數字，那么陣列排序后該數字一定位于陣列中間（中位數），于是可以利用O(n)的查找第K(=n/2)大的演算法，

/**
 * 由于每次 partition 后，pivot 左邊的值都較小，右邊的值都較大，
 * 所以當 pivot 位置為 K 時，pivot 的值為第 K 大的值，
 * 不斷對區間進行劃分使得 pivot 位于 K, 然后檢驗它出現的次數是否大于一半，
 */

public class Solution {
    public int  MoreThanHalfNum_Solution(int [] array) {
        if(array == null||array.length ==0)
            return 0;
        int mid = array.length/2;
        int start = 0, end = array.length-1;
        int index = Partition(array,start,end); // 左閉右閉
        while(index!=mid){
            if(index > mid){
                index = Partition(array,start,index-1);
            }else{
                index = Partition(array,index+1,end);
            }
        }
        int result = array[index];

        if(check(array,result,mid))
            return result;

        return 0;
    }

    private int Partition(int[] arr, int start, int end) {
        int pivot = arr[start];
        int left = start, right = end;
        while (left < right) {
            // 因為pivot取的是最左邊，所以要先從右邊找
            while (left < right && arr[right] >= pivot) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;// left 為最后樞值所在的位置
    }

    private boolean check(int[] arr, int result, int mid){
        int times=0;

        for (int anArr : arr) {
            if (anArr == result)
                times++;
        }
        if(times*2>arr.length)
            return true;
        return false;
    }
}

方法 3：遍歷判斷，兩兩相消

? 如果有符合條件的數字，則它出現的次數比其他所有數字出現的次數和還要多，
? 思路的本質是，將一對不同的數相消，那么符合條件的數字一定是最后留下來的數字，
? 在遍歷陣列時保存兩個值：一是陣列中一個數字，一是次數，遍歷下一個數字時，若它與之前保存的數字相同，則次數加1，否則次數減1；若次數為0，則保存下一個數字，并將次數置為1，遍歷結束后，所保存的數字即為所求，然后再判斷它是否符合條件即可，

/ Q30 連續子陣列的最大和【dp ，Math.max()】

? HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學，今天測驗組開完會后,他又發話了:在古老的一維模式識別中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決，但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)，給一個陣列，回傳它的最大連續子序列的和，你會不會被他忽悠住？(子向量的長度至少是1)

/**
 * dp[i] 為以 array[i] 為末尾的最大子向量和
 * dp[i] = max(dp[i-1]+a[i], a[i])
 */

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array==null||array.length==0)
            return 0;

        int rst = array[0],dp = array[0];

        for(int i=1;i<array.length;i++){
            dp = Math.max(dp+array[i],array[i]);
            rst=Math.max(rst,dp);
        }

        return rst;
    }
}

/ Q32 把陣列排成最小的數【Collections.sort()，Integer.toString(int n)，stringBuilder.append(str)】

? 輸入一個正整數陣列，把陣列里所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個，例如輸入陣列{3，32，321}，則列印出這三個數字能排成的最小數字為321323，

/**
 * 不是比較字典序！
 *
 * 先將整型陣列轉換成String陣列，然后排序，最后將排好序的字串陣列拼接，
 * 關鍵就是制定排序規則:
 * 若ab > ba 則 a > b，
 * 若ab < ba 則 a < b，
 * 若ab = ba 則 a = b；
 * 解釋說明：
 * 比如 "3" < "31"但是 "331" > "313"，所以要將二者拼接起來進行比較
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        if(numbers==null||numbers.length==0)
            return "";
        ArrayList<String> arrayList = new ArrayList<>();
        for(int n:numbers)
            arrayList.add(Integer.toString(n));

        // 重定義 Collections.sort()的排序規則
        Collections.sort(arrayList, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String s1=o1+o2;
                String s2=o2+o1;
                return s1.compareTo(s2); // 回傳的值小于0則表示 s1<s2, s1 排在 s2 前
            }
        });


        StringBuilder rst=new StringBuilder();
        for(String s:arrayList){
            rst.append(s);
        }

        return rst.toString();
    }
}

簡潔寫法如下，暫時還沒看懂，

public String PrintMinNumber(int [] numbers) {
        ArrayList<Integer> list = new ArrayList();
        Arrays.stream(numbers).forEach(list::add);
 
        list.sort((str1, str2) -> {
            String s1 = str1 + "" + str2;
            String s2 = str2 + "" + str1;
            return s1.compareTo(s2);
        });
 
        String s = "";
        for (int j : list) {
            s += j;
        }
 
        return s;
    }

Array.sort() to_string(int n)

/// Q35 陣列中的逆序對

在陣列中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對，輸入一個陣列,求出這個陣列中的逆序對的總數P，并將P對1000000007取模的結果輸出，即輸出P%1000000007

輸入：

題目保證輸入的陣列中沒有的相同的數字資料范圍：對于%50的資料,size<=10^4 對于%75的資料,size<=10^5 對于%100的資料,size<=2*10^5

示例：

1,2,3,4,5,6,7,0的逆序對數為7，

方法 1：歸并排序統計逆序對

歸并排序的遞回程序是，先將區間一分為二，得到兩個有序的左右區間，然后將左右區間合并，

得到有序左右區間的同時可以計算出區間內的逆序數，合并時可以得到區間間的逆序數，區間的逆序數 = 兩個子區間的逆序數之和 + 子區間間逆序數，

歸并時需要借助 O(n)的輔助空間，

public class Solution {
    public int InversePairs(int[] array) {
        if (array == null || array.length == 0)
            return 0;
        int[] arr = array.clone();
        int[] copy = arr.clone();
        int MOD = 1000000007;
        long ans = MergeSort(arr, copy, 0, arr.length, MOD);// [ , )
        return (int) (ans % MOD);
    }

    private long MergeSort(int[] arr, int[] copy, int start, int end, int MOD) {// [ , )
        long count = 0;
        if (start + 1 < end) {
            int mid = (start + end) / 2;
            long a = MergeSort(arr, copy, start, mid, MOD);
            long b = MergeSort(arr, copy, mid, end, MOD);
            long c = Merge(arr, copy, start, mid, end, MOD);
            count = a + b + c;
        }
        return count % MOD;
    }

    private long Merge(int[] arr, int[] copy, int start, int mid, int end, int MOD) {
        long count = 0;
        
        System.arraycopy(arr, start, copy, start, end - start);
        int i = start, j = mid, k = start;
        while (i < mid && j < end) {
            if (copy[i] <= copy[j]) {
                arr[k++] = copy[i++];
            } else {
                count += (mid - i);
                arr[k++] = copy[j++];
            }
        }
        while (i < mid) arr[k++] = copy[i++];
        while (j < end) arr[k++] = copy[j++];

        return count % MOD;
    }
}

方法 2：樹狀陣列

也許要加離散化就沒有寫了，

樹狀陣列求逆序數的原理
首先明確樹狀陣列在此問題中維護資訊是某個區間中數字出現的個數，將源資料按其原本順序插入樹狀陣列，第i個數字插入的方式為將樹狀陣列的第a[i]位設為1，同時更新覆寫到它的父區間，Query(a[i])可求得[1, a[i]]的區間和，這恰好代表第i個數字前小于等于它的個數，等于的只可能是自身，故小于它的有Query(a[i])-1個，那么大于它的顯然就有i-1-(Query(a[i])-1) = i-Query(a[i])個

for (int i = 1; i <= n; i++) {
    Update(i, 1);
    ans += i - Query(a[i]);
}

int lowbit(int x) {
    return x & (-x);
}
void Update(int pos, int val) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        c[i] += val;
    }
}
int Query(int pos) {
    int ans = 0;
    for (int i = n; i > 0; i -= lowbit(i)) {
        ans += c[i];
    }
    return ans;
}

參考：https://blog.csdn.net/Tc_To_Top/article/details/79562501

/ Q37 數字在排序陣列中出現的次數【二分查找寫法分析，equal_range()】

默認是升序，

方法 1：手寫二分查找，搜索 k-0.5和 k+0.5

（注意：如果查找的數在陣列中存在，這種二分寫法是會回傳錯誤的）

/**
 * 由于是有序陣列中查找，考慮二分；
 * 由于是整數，所以可以稍微變一下，搜索k-0.5和k+0.5
 * 兩個位置相減，即為k出現的次數
 */
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null||array.length==0)
            return 0;
        return BiSearch(array, k+0.5) - BiSearch(array, k-0.5) ;
    }

    private int BiSearch(final int[] array,double x){
        // 回傳第一個大于x的數的位置
        int left=0,right = array.length-1,mid;
        while(left<=right){
            mid= (right-left)/2+left;
            if(array[mid]<=x)// 如果需要的是第一個大于等于x的數的位置呢？
                left=mid+1;
            else
                right=mid-1;

        }
        return left;
    }
}

二分寫法的思路分析：
由于要回傳第一個大于等于x的數的位置，用最后的left指定為目標位置，初始范圍為[0, array.length]（因為沒有查找到時該回傳陣列end），查找程序中，當
① a[mid] <x 時，a[mid] 在目標左側，left = mid+1
② a[mid] >x 時，a[mid] 在目標右側，right = mid-1；
③ a[mid]==x 時，a[mid] 可能為目標，也可能在目標右側，right = mid，
最后，當區間內只有兩個元素時，若left所指為目標，right左移，否則left右移，兩者重合結束查找，

二分總結

二分查找當查找的任務不同時，left = mid 或者 left = mid + 1 或者 right = mid 或者right = mid + 1 的寫法是不同的，要分情況討論，原則是 left 與 right 的賦值要保證目標在 [left, right]內，最后，考慮區間長度為2時的情況，然后給定回圈結束條件是 left <= right，還是 left < right，

//搜索k和k+1
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null||array.length==0)
            return 0;
        return BiSearch(array, k+1) - BiSearch(array, k) ;
    }

    private int BiSearch(final int[] array,int x){
        // 回傳第一個大于等于x的數的位置
        int left=0,right = array.length,mid;
        //為了使得當元素在陣列中不存在時回傳正確 right != array.length-1
        while(left<right){
            mid= (right-left)/2+left;
            if(array[mid]<x)
                left=mid+1;
            else
                right=mid;
        }
        return left;
    }
}

方法 2：C++ STL equal_range()

lower_bound(begin, end,val): 回傳容器中第一個大于或等于val的元素的 iterator 位置，
upper_bound(begin, end, val): 回傳容器中第一個大于val的元素的 iterator 位置，
binary_search(begin, end, val): 回傳容器中是否有元素等于val，
equal_range(begin, end, val): 回傳 lower_bound和upper_bound的 pair，

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto resultPair = equal_range(data.begin(), data.end(),k);
        return resultPair.second - resultPair.first;
    }
};

// Q40 找出陣列中兩個只出現一次的數字【位運算】

一個整型陣列里除了兩個數字之外，其他的數字都出現了兩次，請寫程式找出這兩個只出現一次的數字，

我們知道，如果只有一個數字出現一次的話，所有元素異或結果便是該數，
在本題，所有元素異或結果為兩個數的異或結果，顯然，我們無法從兩個數的異或結果中推匯出原來的數，
但是，若異或結果二進制中某bit為1，說明那兩個數該bit上一定不同，由此可以把陣列中的數分為兩類，一類該bit為0，一類該bit為1，要找的兩個數一定分別在兩類中，把兩類數分別異或，就得到了結果，

//num1,num2分別為長度為1的陣列，傳出引數
//將num1[0],num2[0]設定為回傳結果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array == null || array.length==1)
            return ;

        int xor = 0;
        for(int x:array){
            xor^=x;
        }

        if (xor == 0)
            return;

        int fisrtBit = (xor&(xor-1))^xor;// 結合上次學到的 n&(n-1) ，找到第一個為1 的bit ^. ^  ，或者 Xor&~(Xor - 1)
        
        num1[0]=num2[0]=0;
        for(int x:array){
            if((x&fisrtBit)!=0) num1[0]^=x;
            else num2[0]^=x;
        }
    }
}

拓展：陣列a中只有一個數出現一次，其他數字都出現了3次，找出這個數字

申請了32位陣列,然后把原陣列中的每一個數字,展開成二進制,哪一位為1,那么bits[]那一位就+1. 最終,判斷bit中每一位是否是3的倍數(或者是0),如果是,那么我們要找的數字在這一位肯定為0,反之為1

/**
     * 陣列a中只有一個數出現一次，其他數字都出現了3次，找出這個數字
     * @param a
     * @return
     */
public static int find1From3(int[] a){
    int[] bits = new int[32];
    int len = a.length;
    for(int i = 0; i < len; i++){
        for(int j = 0; j < 32; j++){
            bits[j] = bits[j] + ( (a[i]>>>j) & 1);
        }
    }
    int res = 0;
    for(int i = 0; i < 32; i++){
        if(bits[i] % 3 !=0){
            res = res | (1 << i);
        }
    }
    return res;
}

/ Q50 陣列中重復的數字【不借助輔存】

在一個長度為n的陣列里的所有數字都在0到n-1的范圍內，
陣列中某些數字是重復的，但不知道有幾個數字是重復的，也不知道每個數字重復幾次，請找出陣列中任意一個重復的數字，
例如，如果輸入長度為7的陣列{2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數字2，

當一個數字被訪問過后，可以設定對應位上的數值 + n，之后再遇到相同的數時，會發現對應位上的數已經大于等于n了，那么直接回傳這個數即可，

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        for( int i=0;i<length;i++){
            int val=numbers[i];
            if(val>=length) val-=length;
            if(numbers[val]>=length){
                duplication[0]=val;
                return true;
            }
            numbers[val]+=length;
        }
        
        return false;
    }
}

Q51 構建乘積陣列

給定一個陣列A[0,1,...,n-1],請構建一個陣列B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]，不能使用除法，

先順著乘，再倒著乘，

public class Solution {
    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        if (B.length != 0) B[0] = 1;
        for (int i = 1; i < B.length; i++) {
            B[i] = B[i - 1] * A[i - 1];
        }

        int temp = 1;
        for (int j = B.length - 2; j >= 0; j--) {
            temp *= A[j + 1];
            B[j] *= temp;
        }
        return B;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138125.html

標籤：其他

上一篇：樹的資料結構

下一篇：金額必須保留兩位小數？

《劍指offer》陣列專題 (牛客10.22)

// Q01 二維部分有序陣列查找 【善用性質】

// Q06 旋轉陣列中的最小元素 【二分 || 暴力】