題目描述 最近事情比較少，空閑比較多，就刷刷劍指Offer上的經典題。把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出 ...
題目描述
最近事情比較少，空閑比較多，就刷刷劍指Offer上的經典題。把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。 輸入一個非減排序的數組的一個旋轉，輸出旋轉數組的最小元素。 例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。 NOTE：給出的所有元素都大於0，若數組大小為0，請返回0。
解題思路
旋轉數組：給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。
二分法：對於區間[a，b]上連續不斷且f（a）·f（b）<0的函數y=f（x），通過不斷地把函數f（x）的零點所在的區間一分為二，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫二分法。
這道題最簡單的做法就是整個數組遍歷一遍，找出最小的值，但是這個就沒有利用旋轉數組的特性了，根據旋轉數組的特性，這個數組優勢非減排序的，那麼最小的那個值剛好是旋轉數組的分界線，在排序中我們可以用二分法實現最小值得查找。
代碼實現
旋轉數組：給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉,k為3
public static int[] Rotate(int[] data, int k) { if (data == null) return data; int temp = 0, length = data.Length; k = k % length; for (int i = 0; i < k; i++) { //依次後移 temp = data[length - 1]; for (int j = length - 1; j > 0; j--) { data[j] = data[j - 1]; } data[0] = temp; } return data; }
優化的旋轉數組
public static int[] Rotate2(int[] nums, int k) { // 處理 k 大於 數組長度的情況 k = k % nums.Length; // 對前 n - k 個元素 [1,2,3,4] 進行逆轉後得到 [4,3,2,1] reverse(nums, 0, nums.Length - 1 - k); //對後k個元素 [5,6,7] 進行逆轉後得到 [7,6,5] reverse(nums, nums.Length - k, nums.Length - 1); // 將前後元素 [4,3,2,1,7,6,5] 逆轉得到：[5,6,7,1,2,3,4] reverse(nums, 0, nums.Length - 1); return nums; void reverse(int[] nums2, int start, int end) { while (start < end) { int temp = nums2[start]; nums2[start++] = nums2[end]; nums2[end--] = temp; } } }
最簡單的方法實現查找最小值
public static int MinForSimple(int[] data) { if (data == null) return 0; int temp = data[0]; for (int i = 1; i < data.Length; i++) { if (data[i] < temp) { temp = data[i]; } } return temp; }
二分法查找最小值
public static int MinForBinary(int[] data) { if (data == null) return 0; int left = 0; int right = data.Length - 1; var mid = 0; while (left < right) { mid = (left + right) / 2; if (data[mid] > data[right]) left = mid + 1; else if (data[mid] < data[right]) right = mid; else right = mid; } return data[left]; }
把一個數組的偶數排在前面奇數排在後面
public static int[] OddAndEven(int[] data) { if (data == null) return data; int i = 0,j = data.Length - 1; for (i = 0; i <= j; i++) { if (data[i] % 2 == 1)//奇數判斷 { for (int k = j; k > i; k--) { if (data[k] % 2 == 0)//偶數判斷 { j = k; var temp = data[i]; data[i] = data[k]; data[k] = temp; break; } } } } return data; }
想入非非：擴展思維，發揮想象
1. 熟悉二分法
2. 熟悉旋轉數組
3. 把一個數組的偶數排在前面奇數排在後面
測試
using CodingInterviews; using System; using System.Collections.Generic; using System.Text; using Xunit; namespace CodingTest { public class Coding006Test { /// <summary> /// 奇數 /// </summary> [Fact] public void Test1() { int[] array = { 3, 4, 5, 1, 2 }; Assert.Equal(1, Coding006.MinForBinary(array)); Assert.Equal(1, Coding006.MinForSimple(array)); } /// <summary> /// 偶數 /// </summary> [Fact] public void Test2() { int[] array = { 3, 4, 5, 1 }; Assert.Equal(1, Coding006.MinForBinary(array)); Assert.Equal(1, Coding006.MinForSimple(array)); } /// <summary> /// 正序 /// </summary> [Fact] public void Test3() { int[] array = { 1, 2, 3, 4, 5 }; Assert.Equal(1, Coding006.MinForBinary(array)); Assert.Equal(1, Coding006.MinForSimple(array)); } /// <summary> /// 單數 /// </summary> [Fact] public void Test4() { int[] array = { 1}; Assert.Equal(1, Coding006.MinForBinary(array)); Assert.Equal(1, Coding006.MinForSimple(array)); } /// <summary> /// 偶數 /// </summary> [Fact] public void Test5() { int[] array = { 1,2 }; Assert.Equal(1, Coding006.MinForBinary(array)); Assert.Equal(1, Coding006.MinForSimple(array)); } [Fact] public void Test6() { int[] array = { 2, 1 }; Assert.Equal(1, Coding006.MinForBinary(array)); Assert.Equal(1, Coding006.MinForSimple(array)); } [Fact] public void Test7() { int[] array = { 3, 4, 5, 2, 2, 2 }; Assert.Equal(2, Coding006.MinForBinary(array)); Assert.Equal(2, Coding006.MinForSimple(array)); } [Fact] public void Test8() { int[] array = { 1, 0, 1, 1, 1 }; Assert.Equal(0, Coding006.MinForBinary(array)); Assert.Equal(0, Coding006.MinForSimple(array)); } } }View Code
