一、852.⼭脉数组的峰顶索引

题目链接：852.⼭脉数组的峰顶索引
题目描述：

题目解析：

• 给我们一个数组，元素是先递增在递减的，让我们返回最大元素下标。

1.1 二分查找

解题思路：

• 我们这个数组本来就是一个被天然分成两段，递增区间和递减区间，的数据，天然使用二分查找的题。
• 当mid的元素小于后一个元素的时候，mid在递增区间，所以left = mid + 1。
• 当mid的元素大于后一个元素的时候，mid在递减区间，所以right = mid。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 0;int right = arr.length-1;while(left < right) {int mid = left + (right - left) / 2;if(arr[mid] < arr[mid+1]) left = mid + 1;else right = mid;}return left;}
}

1.2 暴力枚举

解题思路：

• 直接使用for循环遍历数组，该下标元素大于前面和后面元素，返回下标。
• 因为这个数组一定是一个山脉数组，所以不用管数组头和尾。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int peakIndexInMountainArray(int[] arr) {for(int i = 1; i < arr.length - 1; i++) {if(arr[i] > arr[i-1] && arr[i] > arr[i+1]) return i;}return 0;}
}

二、162.寻找峰值

题目链接：162.寻找峰值
题目描述;

题目解析：

• 给我们的数组是，递增递减反复进行，让我们找到其中一个峰值的下标。
• 数组可能是这几个情况：1 . /\/\/\ ，2. / ，3. \

2.1 二分查找

解题思路：

• 其实我们可以将数组分为，有要求峰值和没有要求峰值两段，因为给了峰值不等于下一个元素。
• 所以当mid小于下一个元素的时候，mid就是在没有要求峰值那段，left = mid+1。
• 当mid大于下一个元素的时候，mid就是在有峰值那段，right = mid

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {public int findPeakElement(int[] nums) {int left = 0;int right = nums.length - 1;while(left < right) {int mid = left + (right - left) / 2;if(nums[mid] < nums[mid + 1]) left = mid + 1;else right = mid; }return left;}
}

2.2 暴力枚举

解题思路：

• 直接转变为求数组最大值下标，遍历数组即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int findPeakElement(int[] nums) {int ret = 0;for(int i = 0; i < nums.length; i++) {if(nums[i] > nums[ret])  ret = i;}return ret;}
}

三、153.寻找旋转排序数组中的最⼩值

题目链接：153.寻找旋转排序数组中的最⼩值
题目描述：

题目解析：

• 数组旋转一次就代表将数组尾元素放在数组头。
• 给我们一个原来升序的数组，旋转多次后，找到数组中最小元素下标。
• 数组中元素各不相同。
• 数组会是下面这种状态或者一个完全递增的状态
  

3.1 二分查找

解题思路：

• 我们这个数组本来就是已经是被分成两段了的。
• 我们可以使用nums[ 0 ]或者nums[ nums.length - 1 ]来当分界线。
• 使用nums[ nums.length - 1 ]为界限：
• • mid元素大于等于界限时，在数组段1，所以left = mid + 1。
• • mid元素小于界限的时候，在数组段2，所以right = mid。
• 使用nums[ 0 ]为界限：
• • mid元素大于等于界限时，在数组段1，所以left = mid + 1。
• • mid元素小于界限的时候，在数组段2，所以right = mid。
• • 考虑数组完全递增时，nums[0]才是最小值。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
//使用nums[ nums.length - 1 ]为界限：
class Solution {public int findMin(int[] nums) {int left  = 0;int right = nums.length - 1;while(left < right) {int mid = left + (right - left) / 2;if(nums[mid] < nums[nums.length-1]) right = mid;else left = mid + 1;}return nums[left];}
}
//使用nums[ 0 ]为界限：
class Solution {public int findMin(int[] nums) {int left  = 0;int right = nums.length - 1;while(left < right) {int mid = left + (right - left) / 2;if(nums[mid] >= nums[0]) left = mid + 1;else right = mid;}if(nums[0] < nums[left]) left = 0;return nums[left];}
}

3.2 暴力枚举

解题思路;

• 直接循环遍历数组找最小值即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int findMin(int[] nums) {int ret = nums[0];for(int i = 0; i < nums.length; i++) {if(nums[i] < ret) ret = nums[i];}return ret;}
}

四、LCR 173.点名

题目链接：LCR 173.点名
题目描述：

题目解析：

• 给你一个长度为n数组，这个数组中有0到n中的数，按升序排列，找出数组在0到n中不含有的数。

4.1 二分查找

解题思路：

• 这个数组分为这样两段，一段是下标与元素值相同的，一段是下标是元素值减1。
• 所以当mid元素等于mid的时候，落在第一段，left = mid + 1;
• 当mid元素不等于mid的时候，落在第二段，right = mid。

解题代码：

//时间复杂度：O(logN)
//空间复杂度：O(1)
class Solution {public int takeAttendance(int[] records) {int left = 0;int right = records.length;while(left < right) {int mid = left + (right - left) / 2;if(records[mid] == mid) left = mid + 1;else right = mid;}return left;}
}

4.2 哈希表

解题思路：

• 借助一个数组来标记0到n中出现过的元素。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {public int takeAttendance(int[] records) {int[] hash = new int[records.length + 1];for(int i = 0; i < records.length; i++) {hash[records[i]]++;}for(int i = 0; i < hash.length; i++) {if(hash[i] == 0) return i;}return 0;}
}

4.3 暴力枚举

解题思路：

• 直接遍历数组，当出现第一个下标和元素不相等的直接返回元素减一即可。
• 遍历完数组还是没找到，证明是0到n中n不在数组中。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int takeAttendance(int[] records) {for(int i = 0; i < records.length; i++) {if(records[i] != i) return records[i]-1;}return records.length;}
}

4.4 位运算

解题思路：

• 直接使用一个变量来将0到n的数全部异或。
• 在于数组元素进行异或。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int takeAttendance(int[] records) {for(int i = 0; i < records.length; i++) {if(records[i] != i) return records[i]-1;}return records.length;}
}

4.5 数学（求和）

解题思路：

• 直接先将0到n的和求出来。
• 在减去数组中的元素即可。

解题代码：

//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {public int takeAttendance(int[] records) {int n = records.length;int ret = (n*(n+1))/2;for(int i = 0; i < records.length; i++) {ret = ret - records[i];}return ret;}
}