【算法】解題總結：劍指Offer 6 旋轉數組的最小數字、劍指Offer 16 合并兩個排序的連結清單

JZ6 旋轉數組的最小數字

（簡單）

題目

描述

把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。

輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。

NOTE：給出的所有元素都大于0，若數組大小為0，請傳回0。

示例

輸入：

[3,4,5,1,2]

傳回值：

1

思路

本題中關于此原始數組的其中一個描述是非遞減排序的數組，這個名詞我們千萬不能了解錯了，非遞減排序的正确意思是，資料遞增排列，但并非單調遞增（因為可能有多個相等的資料的情況），即數列整體上從小到大并且允許其中有相等的情況出現。

而此題中的旋轉數組，也就是根據非遞減排序的數組經過旋轉生成的，是以，針對 [1, 2, 3, 4, 5]這樣一個非遞減排序的數組，經過旋轉後的全部可能排列情況為：

12345

23451

34512

45123

51234      

因為旋轉後的數組，在整體上，仍是有序的，并且這種有序的性質是可能集中有序于左部分，或右部分，是以，我們不難聯想到二分法，我們完全可以定義一個 start 起始下标，end 末尾下标，mid 中間下标。我們在編碼的循環中，以 start != end 為終止循環的條件，并在循環體中不斷縮小查找範圍，最終定位最小元素值。接下來我們便可以根據上面的排序樣例分析，在循環體中，如果中值大于尾值，那麼我們可以判定最小值在位置的右半部分，并且最小值不可能是中值或者說不可能和中值相等，是以我們便可将頭值下标指向中值下标的下一位，若中值小于尾值，則最小值在左部分，并且需将尾下标指向中值下标，因為中值也在最小值的可能範圍内。最後還需注意的一點就是題目中的 NOTE：若數組大小為0，則傳回0。

上述算法思想也可以再進行進一步的優化，就12345這種排序情況，我們沒必要再進入循環體比較，因為此題情況特殊，是由非遞減排序的數組而生成的旋轉數組，是以，當程式遇到這種整體遞增（可能有等值，但不影響）的情況，隻需通過 array[start] 小于 array[end] 成立，即可判斷為此種情況，直接傳回頭值即可。另外，如果在其他情況中，循環體中出現了 array[mid] 等于 array[end] 的情況（這也意味着原始的非遞減排序有資料相等的情況出現），我們可将尾下标進行一次左移動，進而避免之後不必要的判斷，提高算法的執行效率，而此題也是卡的這一點，因為我在用 Java 代碼進行送出時，沒有這一步優化是會運作逾時的。

實作

class Solution3 {
    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        int start = 0;
        int end = array.length - 1;
        int mid = 0;
        while (start != end) {

            // 優化1
            if (array[start] < array[end]) {
                return array[start];
            }
            //

            mid = (start + end) / 2;
            if (array[mid] > array[end]) {
                start = mid + 1;
            } else if (array[mid] < array[end]) {
                end = mid;
            }

            // 優化2
            else {
                end--;
            }
            //
        }
        return array[start];
    }
}

public class JZ6旋轉數組的最小數字 {
    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        int[] array = new int[]{3, 4, 5, 1, 2};
        int[] array2 = new int[]{4, 5, 1, 2, 3};
        int[] array3 = new int[]{5, 1, 2, 3, 4};
        int[] array4 = new int[]{3, 4, 1, 2};
        int[] array5 = new int[]{2, 1};
        int[] array6 = new int[]{1, 2, 3, 4};
        System.out.println(solution3.minNumberInRotateArray(array));
        System.out.println(solution3.minNumberInRotateArray(array2));
        System.out.println(solution3.minNumberInRotateArray(array3));
        System.out.println(solution3.minNumberInRotateArray(array4));
        System.out.println(solution3.minNumberInRotateArray(array5));
        System.out.println(solution3.minNumberInRotateArray(array6));
    }
}      

JZ16 合并兩個排序的連結清單

（簡單）

題目

描述

輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足單調不減規則。

示例

輸入：

{1,3,5},{2,4,6}

傳回值：

{1,2,3,4,5,6}

思路

此題為常見的兩連結清單合并操作，隻是在合并的同時要求結點值單調不遞減。

實作

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

class Solution6 {
    public static ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        } else if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else {
            ListNode mergeList = new ListNode(0);
            ListNode tempList = mergeList;
            while (list1 != null && list2 != null) {
                if (list1.val > list2.val) {
                    tempList.next = new ListNode(list2.val);
                    tempList = tempList.next;
                    list2 = list2.next;
                } else {
                    tempList.next = new ListNode(list1.val);
                    tempList = tempList.next;
                    list1 = list1.next;
                }
            }
            while (list1 != null) {
                tempList.next = new ListNode(list1.val);
                tempList = tempList.next;
                list1 = list1.next;
            }
            while (list2 != null) {
                tempList.next = new ListNode(list2.val);
                tempList = tempList.next;
                list2 = list2.next;
            }
            return mergeList.next;
        }
    }
}

public class JZ16合并兩個排序的連結清單 {
    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        //ListNode OList1 = list1;
        //list1 = list1.next;
        //list1 = new ListNode(3);
        //list1 = list1.next;
        //list1 = new ListNode(5);
        list1.next = new ListNode(3);
        list1.next.next = new ListNode(5);

        ListNode list2 = new ListNode(2);
        //ListNode OList2 = list2;
        //list2 = list2.next;
        //list2 = new ListNode(4);
        //list2 = list2.next;
        //list2 = new ListNode(6);
        list2.next = new ListNode(4);
        list2.next.next = new ListNode(6);

        ListNode merge = Solution6.Merge(list1, list2);

        showList(merge);
    }

    private static void showList(ListNode merge) {
        while (merge != null) {
            System.out.print(merge.val);
            if (merge.next != null) {
                System.out.print("——");
            }
            merge = merge.next;
        }
    }
}