查找&排序合集

快排

C++

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        QuickSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void QuickSort(vector<int>& nums, int left, int right){
        if(left < right){
            int pos = Random_Partition(nums, left, right);
            QuickSort(nums, left, pos - 1);
            QuickSort(nums, pos + 1, right);
        }
    }

    int Partition(vector<int>& nums, int left, int right){
        int temp = nums[left];
        while(left < right){
            while(left < right && nums[right] >= temp) right --;
            nums[left] = nums[right];
            while(left < right && nums[left] <= temp) left ++;
            nums[right] = nums[left];
        }
        nums[left] = temp;
        return left;
    }
    
    // 更快版本的Partition
    int Partition2(vector<int>& a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] < x) {
                swap(a[++i], a[j]);
            }
        }
        swap(a[i + 1], a[r]);
        return i + 1;
    }
    
    // 优化，随机取 temp
    //int Random_Partition(vector<int>& nums, int left, int right) {
    //    int i = rand() % (right - left + 1) + left; // 随机选一个作为我们的主元
    //    swap(nums[left], nums[i]);
    //    return Partition(nums, left, right);
    //}
};

归并排序

C++

void merge_sort(vector<int> a, int l, int r){
	if(l < r){
		int mid = (l + r) / 2;//从中间截开
		merge_sort(a, l, mid);//把左边沿中间截开
		merge_sort(a, mid + 1, r);//把右边沿中间截开
		merge(a, l, r, mid);//合并
	}
}

void merge(vector<int> a, int l, int r, int mid) {
	vector<int> s();//一个新数组用来存储排序好的数组
	int i = l, j = mid + 1;//两个变量分别指向左边和右边两组数的第一个数
	while (i <= mid && j <= r) {
		if (a[i] < a[j]) s.push_back(a[i++]);
		else s.push_back(a[j++]);
	}
	while (i <= mid) s.push_back(a[i++]);//当一组数已经全部排进去之后，再将另外一组数的全部数字都排进去
	while (j <= r)  s.push_back(a[j++]);
	a.assign(s.begin(), s.end());
}

704. 二分查找

C++

• while(l < r)
• if <, l = mid + 1; else r = mid;
• return l

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        while(l < r){
            int mid = (l + r)/2;
            if(nums[mid] < target) l = mid + 1;
            else r = mid;
        }
        return nums[l] == target ? l : -1;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

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

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

C++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int res = search(nums, target);
        if(res == -1) return{-1, - 1};
        int l = res;
        int r = res;
        while(l > 0 && nums[l - 1] == target)    l --;
        while(r < nums.size() - 1 && nums[r + 1] == target)    r ++;
        return{l, r};
    }

    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            int mid = (l + r)/2;
            if(nums[mid] < target) l = mid + 1;
            else if(nums[mid] > target) r = mid - 1;
            else if(nums[mid] == target) return mid;
        }
        return -1;
    }
};

153. 寻找旋转排序数组中的最小值

已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 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 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数 互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

C++

左值 < 中值, 中值 < 右值 ：没有旋转，最小值在最左边，可以收缩右边界
        右
     中
 左
    
左值 > 中值, 中值 < 右值 ：有旋转，最小值在左半边，可以收缩右边界
 左       
         右
     中
    
左值 < 中值, 中值 > 右值 ：有旋转，最小值在右半边，可以收缩左边界
     中  
 左 
         右
    
左值 > 中值, 中值 > 右值 ：单调递减，不可能出现
 左
    中
        右

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        while(l < r){
            int mid = (l + r)/2;
            if(nums[mid] < nums[r]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};

33. 搜索旋转排序数组

整数数组 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
• -104 <= nums[i] <= 104
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        while(l < r){
            int mid = (l + r)/2;
            if(nums[mid] == target)   return mid;
            else if(nums[mid] < nums[r]){ // 如果中间的数小于最右边的数，则右半段是有序的
                if(nums[mid] < target && target <= nums[r]) l = mid + 1; // 不知道第二个条件有什么用
                else r = mid;
            }
            else{ // 若中间数大于最右边数，则左半段是有序的
                if(target < nums[mid] && nums[l] <= target) r = mid; 
                else l = mid + 1;
            }
        }
        return nums[l] == target ? l : -1;
    }
};

852. 山脉数组的峰顶索引

符合下列属性的数组 arr 称为 山脉数组 ：
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]
给你由整数组成的山脉数组arr，返回任何满足arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]的下标 i

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

示例 4：

输入：arr = [3,4,5,1]
输出：2

示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

提示：

• 3 <= arr.length <= 104
• 0 <= arr[i] <= 106
• 题目数据保证 arr 是一个山脉数组

C++

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int l = 0; 
        int r = arr.size() - 1;
        while(l < r){
            int mid = (l + r)/2;
            cout << mid << endl;
            // 不用判断是否越界是因为用例一定是个山脉数组，一定有山峰 不会出现像【0，1，2】或【2，1，0】的用例
            if(arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) return mid; //左右都小于mid，说明mid是山峰
            else if(arr[mid + 1] > arr[mid]) l = mid; //右边比左边高，说明山峰在右侧
            else if(arr[mid + 1] < arr[mid]) r = mid; //右边比左边低，山峰在左侧
        }
        return 89182;  // 随便写，不会执行到这步
    }
};