1.旋轉(zhuǎn)數(shù)組（189 - 中）
題目描述：給定一個數(shù)組怠肋，將數(shù)組中的元素向右移動 k 個位置，其中 k 是非負(fù)數(shù)蹦狂。進(jìn)階：
- 盡可能想出更多的解決方案喘批，至少有三種不同的方法可以解決這個問題。
- 你可以使用空間復(fù)雜度為 O(1) 的 原地 算法解決這個問題嗎椭更？
示例 :
輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]
思路：多解法哪审，其中使用額外數(shù)組，空間復(fù)雜度O(N)虑瀑，其余O(1)湿滓。
- 使用額外數(shù)組：遍歷原數(shù)組，將原數(shù)組下標(biāo)為 ii 的元素放至新數(shù)組下標(biāo)為 (i+k)%n 的位置舌狗，最后將新數(shù)組拷貝至原數(shù)組即可叽奥。
- 模擬循環(huán)：用一個變量tmp維護(hù)移動k次，注意移動數(shù)組時倒序進(jìn)行填充把夸，防止覆蓋而线，時間復(fù)雜度O(kn)铭污，但是超時恋日。
- 數(shù)組翻轉(zhuǎn)：比較巧妙膀篮，先整體翻轉(zhuǎn)，在將0 ~ k - 1和k - 1 ~ n - 1進(jìn)行翻轉(zhuǎn)岂膳。
代碼實現(xiàn)：
class Solution {
// 使用輔助數(shù)組
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] tmp = new int[n];
for (int i = 0; i < n; i++) {
tmp[(i + k) % n] = nums[i];
}
System.arraycopy(tmp, 0, nums, 0, n);
}
// 模擬移動（超時Ｊ母汀）
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
for (int i = 0; i < k; i++) {
int temp = nums[n - 1];
for (int j = n - 1; j > 0; j--) {
nums[j] = nums[j - 1];
}
nums[0] = temp;
}
}
// 數(shù)組翻轉(zhuǎn)（先整體翻轉(zhuǎn)，再翻轉(zhuǎn)部分）
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
j--;
}
}
}
2.尋找旋轉(zhuǎn)排序數(shù)組中的最小值（153 - 中）
題目描述：整數(shù)數(shù)組 nums 按升序排列谈截，數(shù)組中的值 互不相同 筷屡。請你找出并返回數(shù)組中的 最小元素 。
示例 :
輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數(shù)組為 [1,2,3,4,5] 簸喂，旋轉(zhuǎn) 3 次得到輸入數(shù)組毙死。
思路：本題可以直接遍歷獲取最小值，但是考察點二分查找喻鳄。注意體會二分查找的思想扼倘，不要背模板，這里可以畫個折線看看除呵。
注：代碼中比較元素取數(shù)組最后一個元素再菊，也可以取任意一個元素。
代碼實現(xiàn)：
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] > nums[r]) {
l = mid + 1;
} else {
r = mid;
}
}
return nums[l];
}
3.尋找旋轉(zhuǎn)排序數(shù)組中的最小值II（154 - 難）
題目描述：整數(shù)數(shù)組 nums 按升序排列颜曾，數(shù)組中的值 可能存在重復(fù)值 纠拔。返回數(shù)組中的 最小元素 。同 劍指 Offer 11. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
示例 :
輸入：nums = [2,2,2,0,1]
輸出：0
思路：本題可以直接遍歷獲取最小值泛豪，但是考察點二分查找稠诲，與上題不同的是數(shù)組中可能含有重復(fù)值，但是二分的本質(zhì)是二段性候址，并非單調(diào)性吕粹，所以我們還以使用二分。但時間復(fù)雜度可能退化O(n)岗仑，即全部是一種元素匹耕。
注意：由于重復(fù)元素的存在，我們并不能確定 nums[mid]究竟在最小值的左側(cè)還是右側(cè)荠雕，因此我們不能莽撞地忽略某一部分的元素稳其。我們唯一可以知道的是，由于它們的值相同炸卑，所以無論 nums[r] 是不是最小值既鞠，都有一個它的「替代品」nums[mid]，因此我們可以忽略二分查找區(qū)間的右端點盖文。
代碼實現(xiàn)：
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] > nums[r]) {
l = mid + 1;
} else if (nums[mid] < nums[r]){
r = mid;
} else {
r--;
}
}
return nums[l];
}
4.搜索旋轉(zhuǎn)排序數(shù)組（33 - 中）
題目描述：整數(shù)數(shù)組 nums 按升序排列嘱蛋，數(shù)組中的值 互不相同 。
給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個整數(shù) target ，如果 nums 中存在這個目標(biāo)值 target 洒敏，則返回它的下標(biāo)龄恋，否則返回 -1 。
示例 :
輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4
思路：本題考查二分查找凶伙，但是二分查找要求數(shù)組有序郭毕，關(guān)鍵：
- 先通過mid和nums[r]（任意元素）比較確定有序區(qū)間在mid左邊還是右邊, 如T153
- 再確定目標(biāo)元素target在哪邊!，這時我們就可以直接根據(jù)target位置進(jìn)行二分查找了函荣。
代碼實現(xiàn)：
class Solution {
// 直接搜索
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
}
return -1;
}
// 二分查找
public int search(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] == target) return mid;
if (nums[mid] > nums[r]) {
if (target >= nums[l] && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}
5.搜索旋轉(zhuǎn)排序數(shù)組II（81 - 中）
題目描述：整數(shù)數(shù)組 nums 按升序排列（單調(diào)不減）显押，數(shù)組中的值 可能存在重復(fù)值 。
給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個整數(shù) target 傻挂，請你編寫一個函數(shù)來判斷給定的目標(biāo)值是否存在于數(shù)組中乘碑。如果 nums 中存在這個目標(biāo)值 target ，則返回 true 金拒，否則返回 false 蝉仇。
示例 :
輸入：nums = [2,5,6,0,0,1,2], target = 0
輸出：true
思路：經(jīng)過上述各題的過度，直接使用二分解法殖蚕。與33題基本相同轿衔。不同的是含有重復(fù)元素。
時間復(fù)雜度：對于這種含重復(fù)元素的二分查找問題睦疫，最壞時間復(fù)雜度O(n)害驹，即整個數(shù)組都是同一個數(shù)，最好時間復(fù)雜度O(nlogn)蛤育。
代碼實現(xiàn)：
public boolean search(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] == target) return true;
if (nums[mid] > nums[r]) {
if (target >= nums[l] && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else if (nums[mid] < nums[r]) {
if (target > nums[mid] && target <= nums[r]) {
l = mid + 1;
} else {
r = mid - 1;
}
} else {
r--;
}
}
return false;
}
6.在排序數(shù)組中查找目標(biāo)值的首尾元素的索引（34 - 中）
題目描述：給定一個按照升序排列的整數(shù)數(shù)組 nums宛官，可能含有重復(fù)值，和一個目標(biāo)值 target瓦糕。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置底洗。如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]咕娄。
要求：你可以設(shè)計并實現(xiàn)時間復(fù)雜度為 O(log n) 的算法解決此問題嗎亥揖？
示例 :
輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]
思路：代碼1在極端情況下，時間復(fù)雜度退化為O(n)圣勒，不符合要求费变，但容易理解，實現(xiàn)簡單圣贸。
其實挚歧，我們只需要找兩個索引即可，大于target - 1的索引（即目標(biāo)值的起始索引）和第一個大于target的數(shù)的索引 - 1吁峻，時間復(fù)雜度O(nlogn)滑负，只調(diào)用了兩次二分查找在张。
代碼實現(xiàn)：
// 代碼1
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] == target) {
int start = mid, end = mid;
while (start >= 0 && nums[start] == target) start--;
while (end < n && nums[end] == target) end++;
return new int[] {start + 1, end - 1};
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return new int[] {-1, -1};
}
// 代碼2
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1;
int leftIdx = binarySearch(nums, target - 1);
int rightIdex = binarySearch(nums, target) - 1;
if (leftIdx <= rightIdex && nums[leftIdx] == target && nums[rightIdex] == target) {
return new int[] {leftIdx, rightIdex};
}
return new int[] {-1, -1};
}
// 返回大于target的第一個索引值
public int binarySearch(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1, ans = nums.length;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] > target) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
return ans;
}
7.面試題：10.03（補(bǔ)充）
題目描述：返回目標(biāo)元素的第一個索引，即索引值最小的那個（如果存在）矮慕，不存在返回-1瞧掺。
示例 :
輸入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
輸出: 8（元素5在該數(shù)組中的索引）
思路：本題是T82和T34的思路的融合，但注意由于數(shù)組是經(jīng)過旋轉(zhuǎn)凡傅，所以不能像T34查找邊界。類似這種情況旋轉(zhuǎn)數(shù)組：[5,5,5,1,2,3,4,5] 目標(biāo)值：5肠缔，返回的是7夏跷，卻不是0。
- 如果左邊索引滿足條件明未，直接返回
- 二分槽华，mid符合，但是我們找最小的趟妥，所以要更新右邊界猫态。
- mid不符合，找升序區(qū)間繼續(xù)二分
代碼實現(xiàn)：
public int search(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1;
while (l <= r) {
if (nums[l] == target) return l;
int mid = l + ((r - l) >> 1);
// 索引mid的值是目標(biāo)值（左邊可能還有更小的索引值）披摄，更新右邊界
if (nums[mid] == target) r = mid;
if (nums[mid] > nums[l]) {
if (target >= nums[l] && target <= nums[mid]) {
r = mid;
} else {
l = mid + 1;
}
} else if (nums[mid] < nums[l]) {
if (target >= nums[mid] && target <= nums[r]) {
l = mid;
} else {
r = mid - 1;
}
} else {
l++;
}
}
return -1;
}
8.山脈數(shù)組的峰頂索引（852 - 易）
題目描述：符合下列屬性的數(shù)組 arr 稱為 山脈數(shù)組 ：
- arr.length >= 3
- 存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
給你由整數(shù)組成的山脈數(shù)組 arr 亲雪，返回任何滿足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下標(biāo) i 。
示例 :
輸入：arr = [0,2,1,0]
輸出：1
思路：本題考察點二分查找疚膊，只不過二分的判斷條件有點不同义辕。即通過mid相鄰點判斷最大值所在區(qū)間。
代碼實現(xiàn)：
public int peakIndexInMountainArray(int[] arr) {
int n = arr.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] < arr[mid + 1]) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
9.山脈數(shù)組中查找目標(biāo)值（1095 - 難）
題目描述：給你一個 山脈數(shù)組 mountainArr寓盗，請你返回能夠使得 mountainArr.get(index) 等于 target 最小 的下標(biāo) index 值灌砖。
如果不存在這樣的下標(biāo) index，就請返回 -1傀蚌。
示例 :
輸入：array = [1,2,3,4,5,3,1], target = 3
輸出：2
解釋：3 在數(shù)組中出現(xiàn)了兩次基显，下標(biāo)分別為 2 和 5，我們返回最小的下標(biāo) 2善炫。
思路：上一題的升級撩幽，我們尋找包含重復(fù)元素的最小索引值。類比面試題10.03箩艺。兩階段：
- 找到最大值索引摸航，T852
- 分別在升序和降序區(qū)間找目標(biāo)值。
時間復(fù)雜度O(nlogn)舅桩，進(jìn)行三次二分查找（也可能兩次）酱虎。
代碼實現(xiàn)：
public int findInMountainArray(int target, MountainArray mountainArr) {
// 1.查找峰頂索引
int n = mountainArr.length();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
l = mid + 1;
} else {
r = mid;
}
}
// 2.對升序和降序數(shù)組分別進(jìn)行二分查找(用flag標(biāo)識升序和降序區(qū)間)
int idx = binarySearch(target, mountainArr, 0, l, true);
return idx != -1 ? idx : binarySearch(target, mountainArr, l + 1, n - 1, false);
}
public int binarySearch(int target, MountainArray mountainArr, int l, int r, boolean flag) {
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (mountainArr.get(mid) == target) return mid;
if (mountainArr.get(mid) < target) {
l = flag ? mid + 1 : l;
r = flag ? r : mid - 1;
} else {
r = flag ? mid - 1 : r;
l = flag ? l : mid + 1;
}
}
return -1;
}
10.兩數(shù)相除（29 - 中）
思路：由于題目限定了我們不能使用乘法、除法和 mod 運算符擂涛。
核心：我們可以先實現(xiàn)一個「倍增乘法」读串，然后利用對于 x 除以 y聊记，結(jié)果 x / y 必然落在范圍 [0, x] 的規(guī)律進(jìn)行二分。
注意：long mid = l + r + 1 >> 1恢暖，之前的用法會超時排监？
public int divide(int a, int b) {
long x = a, y = b;
boolean isNeg = (x < 0 && y > 0) || (x > 0 && y < 0);
if (x < 0) x = -x;
if (y < 0) y = -y;
long l = 0, r = x;
while (l < r) {
long mid = l + r + 1 >> 1;
if (mul(mid, y) <= x) {
l = mid;
} else {
r = mid - 1;
}
}
long ans = isNeg ? -l : l;
if (ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE) return Integer.MAX_VALUE;
return (int)ans;
}
// 倍乘函數(shù)
public long mul(long a, long k) {
long ans = 0;
while (k > 0) {
if ((k & 1) == 1) ans += a;
k >>= 1;
a += a;
}
return ans;
}
