二、二分查找（简）

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

题解

在升序数组nums中寻找目标值target，对于特定下标i，比较nums[i]和target的大小：

  • 如果nums[i] = target，则下标i即为要寻找的下标；
  • 如果nums[i] > target，则target在下标i左侧；
  • 如果nums[i] < target，则target在下标i右侧；

所以，二分查找的做法是，
1、定义查找的范围[left,right]，初始查找范围是整个数组；
2、每次取查找范围的中点mid，比较nums[mid]和target的大小；
3、如果相等则mid即为要寻找的下标，如果不相等则根据nums[mid]和target的大小关系将查找范围缩小一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    int res = -1;
    int left = 0, right = nums.size() - 1;
    while (left < right) {
      int mid = (left + right) / 2;
      if (nums[mid] < target) {
        left = mid + 1;
      } else if (nums[mid] > target) {
        right = mid - 1;
      } else {
        res = mid;
        break;
      }
    }
    return res;
  }
};

二、数组中的第K个最大元素（困）

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

题解1

最简单的，先排序，再取第k个出来，排序的话就用快排，快排也有很多种，下面是双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    int ve_len = nums.size();
    QuickSort(nums, 0, ve_len - 1);
    return nums[ve_len - k];
  }

  // 快排
  void QuickSort(vector<int>& nums, int left, int right) {
    if (left >= right)
      return;
    int pivot = nums[left], i = left, j = right;
    while (i < j) {
      while (i < j && nums[j] >= pivot) {
        j--;
      }
      while (i < j && nums[i] <= pivot) {
        i++;
      }
      std::swap(nums[i], nums[j]);
    }
    std::swap(nums[left], nums[i]);
    QuickSort(nums, left, i - 1);
    QuickSort(nums, j + 1, right);
  }
};

int main() {
  int arr[6] = {3, 1, 5, 6, 4, 7};
  vector<int> nums(begin(arr), end(arr));

  QuickSort(nums, 0, nums.size() - 1);
  for (auto i : nums) {
    cout << i << " ";
  }
  return 0;
}

题解2

既然都想到排序了，何不用大根堆来实现。而且C++自带的优先队列就能实现大根堆，自动帮我们排序
首先回顾下优先队列priority_queue
普通队列是先进先出；而优先队列中具有最高优先级的元素将被首先删除
如下所示，升序队列从大到小排列，top()返回的是最小值，即小根堆；降序队列从小到大排列，top()返回的是最大值，即大根堆

1
2
3
4
// 升序队列
priority_queue <int, vector<int>, greater<int>> q;
// 降序队列
priority_queue <int, vector<int>, less<int>>q;

这道题就可以直接用降序队列，把nums存进队列中，让它自个排序，再取第k个就行

1
2
3
4
5
6
7
8
9
10
11
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, less<int>> maxHeap;
    for (int x : nums)
      maxHeap.push(x);
    for (int i = 0; i < k - 1; i++)
      maxHeap.pop();
    return maxHeap.top();
  }
};

题解3

面试官肯定不希望你调库，所以自己实现大根堆才是加分项
首先要回顾下堆排序，忘记了就回去看这里
大根堆就是根节点一定大过左右节点的值。
这样我们就可以根据给定的数组，创建一个大根堆，让最大的值在栈顶，然后要找第k个最大值,就把堆顶的值和最末尾的子节点互换，并忽略该子节点，重新生成个大根堆，这样堆顶元素就是要求的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();
    build_maxHeap(nums);  // 创建大根堆
    for (int i = 0; i < k - 1; i++) {
      // 求第i个最大值,就把栈顶的值nums[0]和叶子节点nums[n-1-i]调换
      // 除去nums[n-1-i]，剩下其余节点再调整为大根堆
      swap(nums[0], nums[n - 1 - i]);
      adjust_down(nums, 0, n - 1 - i - 1);
    }
    for (auto i : nums) {
      cout << i << " ";
    }
    return nums[0];
  }

  void build_maxHeap(vector<int>& nums) {
    int n = nums.size();
    // 堆排序最后一个非叶子节点(父节点)的序号就是n/2-1
    for (int root = n / 2 - 1; root >= 0; root--) {
      adjust_down(nums, root, n - 1);
    }
  }

  // 向下调整算法
  void adjust_down(vector<int>& nums, int root, int size) {
    // root最开始指向根节点,child是左孩子
    if (root > size)
      return;
    int temp = nums[root];  // 把堆顶存起来
    int child = 2 * root + 1;
    while (child <= size) {
      if (child + 1 <= size && nums[child] < nums[child + 1]) {
        // 有右子树而且右子树更大
        child++;
      }
      if (nums[child] > temp) {
        // 如果child比temp大,child上去填到root的位置,更新root和child,看下一层
        nums[root] = nums[child];
        root = child;
        child = 2 * root + 1;
      } else {
        break;
      }
    }
    // 不管在哪退出循环,最后都要给空位root赋值
    // 如果child > size,把temp放到叶子节点上
    nums[root] = temp;
  }
};

int main() {
  Solution s;
  vector<int> nums = {3, 2, 1, 5, 6, 4};
  int k = 4;
  s.findKthLargest(nums, k);
  return 0;
}

三、搜索旋转排序数组（中）

题目

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：
输入：nums = [1], target = 0
输出：-1

提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4

题解

首先要明白这道题问的是啥，很简单就是从给定的数组中找出target的下标。
那为啥题目描述的花里胡哨的，还有什么旋转呢，主要是怕你想不到，因为要设计O(log n)的算法，单纯暴力搜索肯定是不行的。
那是不是可以用二分法呢？严格来说，标准的二分法只适用于有序数组，但题目给我们的是旋转后的数组，它不是有序的，所以需要对二分法进行修改变形。
这个旋转后的数组有什么特点呢？可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。
所以我们在常规二分查找的时候，可以查看当前mid为分割位置分割出来的两个部分[left, mid]和[mid+1, right]哪个部分是有序的，根据有序的那部分判断出target在不在这个部分。
所以我们在用二分法时有两种情况:
1、若nums[0] ≤ nums[mid]，说明[left, mid]是有序的；

  • 则当nums[0] ≤ target < nums[mid]时target在[left, mid-1]中，
  • 否则在[mid+1, right]中；

2、若nums[0] > nums[mid]，说明[mid+1, right]是有序的；

  • 则当nums[mid] < target ≤ nums[size-1]时target在[mid+1, right]中，
  • 否则在[left, mid-1]中。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class Solution {
     public:
      int search(vector<int>& nums, int target) {
        if (nums.empty()) {
          return -1;
        }
        int n_size = nums.size();
        int left = 0;
        int right = n_size - 1;
        int res = -1;
        while (left <= right) {
          int mid = (left + right) / 2;
          if (nums[mid] == target) {
            res = mid;
            break;
          }
          if (nums[0] <= nums[mid]) {
            if (nums[0] <= target && target < nums[mid]) {
              right = mid - 1;
            } else {
              left = mid + 1;
            }
          } else {
            if (nums[mid] < target && target <= nums[n_size - 1]) {
              left = mid + 1;
            } else {
              right = mid - 1;
            }
          }
        }
        return res;
      }
    };

    int main() {
      Solution s;
      vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
      cout << s.search(nums, 0);
    }

四、搜索旋转排序数组 II（中）

题目

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
你必须尽可能减少整个操作步骤。

示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：


题目数据保证在预先未知的某个下标上进行了旋转

题解

和上一题一样，只不过因为数组中有重复元素，二分查找时可能会有num[left] = num[mid] = num[right]。
比如数组[3,1,2,3,3,3,3]，target = 2，首次二分时无法判断区间[0, 3]和[4, 6]哪个是有序的。
对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。其余的照抄上一题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  int search(vector<int>& nums, int target) {
    if (nums.empty()) {
      return -1;
    }
    int n_size = nums.size();
    int left = 0;
    int right = n_size - 1;
    bool res = false;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (nums[mid] == target) {
        res = true;
        break;
      }
      if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
        left++;
        right--;
      } else if (nums[0] <= nums[mid]) {
        if (nums[0] <= target && target < nums[mid]) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else {
        if (nums[mid] < target && target <= nums[n_size - 1]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
    return res;
  }
};

五、寻找旋转排序数组中的最小值（中）

题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为  的算法解决此问题。

示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：



中的所有整数互不相同
原来是一个升序排序的数组，并进行了至次旋转

题解

首先对于这个旋转数组，它的特点是：
1、以最小值为分界线的左子序列是单调递增的，右子序列也是单调递增的；
2、对于数组中最后一个元素x，左子序列全大于x，右子序列全小于x。
通过nums[mid]和nums[right]比较，判断nums[mid]在左子序列还是右子序列。
有两种情况：
1、如果nums[mid] < nums[right]，则mid在右子序列，即在最小值右边，所以right左移；
2、如果nums[mid] > nums[right]，则mid在左子序列，即在最小值左边，所以left右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int findMin(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
      int mid = (left + right) / 2;
      if (nums[mid] < nums[right]) {
        right = mid;  // right左移
        // 为什么right=mid,而不是right=mid-1;
        // nums[mid]<nums[right]时,有可能nums[mid]本身就是最小值,然后mid-1就错过了,所以不要减1.比如{4,5,1,2,3},如果right=mid-1,则丢失了最小值1
      } else {
        left = mid + 1;  // left右移
        // 为什么low=mid+1,而不是low=mid;
        // 因为我们这题是求最小值,而nums[mid]>nums[right],自然nums[mid]绝对不会是最小值,所以可以+1过滤掉mid这个下标.比如{4,5,6,1,2,3},nums[mid]=6,low=mid+1,刚好nums[low]=1
      }
    }
    return nums[left];
    // 这里返回的是left,所以只能while(left<right).如果返回的是right,就可以while(left<=right)和while(left<right);
    // 因为若循环条件为while(left<=right),则进入最后一个循环的时候,left=right=mid,都指向最小值,接着执行left=mid+1.这时left便跑到mid和right右边一位去了,因此若要用while(left<=right)条件必须返回 nums[right]或者nums[left-1].
  }
};

六、寻找旋转排序数组中的最小值 II（困）

题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。

示例 1：
输入：nums = [1,3,5]
输出：1

示例 2：
输入：nums = [2,2,2,0,1]
输出：0

提示：



原来是一个升序排序的数组，并进行了至次旋转

题解

这道题和上一题区别就在于数组元素是可以重复的，所以对于有重复元素的旋转数组，它的特点是：
1、以最小值为分界线的左子序列是单调递增的，右子序列也是单调递增的（注意区分严格单调递增）；
2、对于数组中最后一个元素x，左子序列全大于或等于x，右子序列全小于或等于x。
同样通过nums[mid]和nums[right]比较，判断nums[mid]在左子序列还是右子序列。只不过因为有重复值，所以多了一种情况。
有三种情况：

  • 如果nums[mid] < nums[right]，则mid在右子序列，即在最小值右边，所以right左移；
  • 如果nums[mid] > nums[right]，则mid在左子序列，即在最小值右左边，所以left右移；
  • 如果nums[mid] = nums[right]，则不能确定mid在左子序列还是右子序列；由于它们的值相同，所以无论nums[right]是不是最小值，都有一个最小值nums[mid]，因此我们可以忽略二分查找区间的右端点。

解释下第3点，比如数组[1,0,1,1,1]，left = 0，right = 4，mid = 2，无法判断mid在在左子序列还是右子序列，我们采用right--解决此问题
那这个操作会不会影响取最小值呢，事实证明不会：

  • 此操作不会使数组越界：因为迭代条件保证了right>left>=0；
  • 此操作不会使最小值丢失：假设nums[right]是最小值，有两种情况：
    • 若nums[right]是唯一最小值：那就不可能满足判断条件nums[mid]==nums[right]，因为mid<right（left!=right && mid=(left + right)/2）；
    • 若nums[right]不是唯一最小值，由于mid<right而nums[mid]==nums[right]，即还有最小值存在于[left,right−1]区间，因此不会丢失最小值。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      class Solution {
       public:
        int findMin(vector<int>& nums) {
          int left = 0;
          int right = nums.size() - 1;
          while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
              right = mid;  // right左移
            } else if (nums[mid] > nums[right]) {
              left = mid + 1;  // left右移
            } else {
              right--;
            }
          }
          return nums[left];
        }
      };
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Share

快来参与讨论吧~

BlogCategoriesTagsArchives
ProjectIMU_PreintegrationLeGO_LOAM
SocialFriendCircleCommentsTravelling
MoreHomePageAbout
©2018 - Felicx 使用 Stellar 创建
总访问 113701 次 | 本页访问 326 次
共发表 83 篇Blog · 总计 127.5k 字