闻风丧胆的算法（一）

🌈个人主页：Rookie Maker
🔥 系列专栏：算法
🏆🏆关注博主，随时获取更多关于IT的优质内容！🏆🏆  

😀欢迎来到小田代码世界~
😁 喜欢的小伙伴记得一键三连哦 ૮(˶ᵔ ᵕ ᵔ˶)ა

• 前言

  一、二分法是什么？

  二、算法构建

  1.算法思路：

   2.例题

  三.差分数组是什么

  四.算法构建

  1.算法思路

  2.例题

前言

在这里，或许你会有不一样的收获，不要一提算法就闻风丧胆，面对困难的最好的方法就是克服

一、二分法是什么？

🌏二分法(折半查找法)也叫做二分查找，顾名思义，就是把数据分成两半，再判断所查找的key在哪一半中，再重复上述步骤知道找到目标target

🌏二分查找（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

二、算法构建

1.算法思路：

二分查找法
int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1;
}

 2.例题

代码如下（示例）

#include <iostream>  
#include <vector>  
  
using namespace std;  
  
int search(vector<int>& nums, int target) {  
    int left = 0;  
    int right = nums.size() - 1;  
  
    while (left <= right) {  
        int mid = left + (right - left) / 2;  
        if (nums[mid] == target) {  
            return mid; // 找到目标值，返回索引  
        } else if (nums[mid] < target) {  
            left = mid + 1; // 目标值在右半部分  
        } else {  
            right = mid - 1; // 目标值在左半部分  
        }  
    }  
  
    return -1; // 未找到目标值，返回-1  
}  
  
int main() {  
    vector<int> nums = {-1, 0, 3, 5, 9, 12};  
    int target = 9;  
    int result = search(nums, target);  
    cout << 下标为 << result << endl;  
    return 0;  
}

三.差分数组是什么

🔥差分数组：是一个用来记录原数组相邻数据间差值的数组。diff[i] = x[i] – x[i-1]，其中，diff[0] = x[0]

🔥前缀和：前缀和是指数组中某个位置之前（包括该位置）所有元素的和。具体地说，对于数组nums，其前缀和数组prefixSum中的每个元素prefixSum[i]表示nums中从索引0到索引i（包含i）的所有元素的和。

四.算法构建

1.算法思路

差分思路：

1. 初始化差分数组：
   • 对于长度为 n 的原数组 nums，创建一个长度为 n 的差分数组 diff。通常，差分数组的第一个元素 diff[0] 与原数组的第一个元素 nums[0] 相同，即 diff[0] = nums[0]。
   • 对于 i 从 1 到 n-1，计算差分数组的每个元素 diff[i]，其值为 nums[i] - nums[i-1]。这样，差分数组中的每个元素表示原数组中相邻元素的差值。
2. 区间修改操作：
   • 当需要对原数组的某个区间 [l, r] 进行加减操作时（假设加上一个值 c），我们只需要修改差分数组中的两个元素：将 diff[l] 增加 c，将 diff[r+1] 减少 c。
   • 这种修改方式是基于差分的性质：一个区间内的所有元素都加上或减去同一个值，可以通过修改区间两端的差分值来实现。
3. 还原原数组：
   • 通过计算差分数组的前缀和，可以还原出修改后的原数组。从 diff[0] 开始，逐个累加差分数组的元素，得到的就是修改后的原数组。
   • 具体来说，对于 i 从 1 到 n-1，计算 nums[i] 的值为 nums[i-1] + diff[i]。这样，nums 数组就包含了所有区间修改操作后的结果。
4. 输出结果：
   • 最后，输出还原后的原数组 nums 即可。 

2.例题

一组数组，修改2次在不同区间，输出修改后的数组，并且时间复杂度为o(1)

#include<iostream>
using namespace std;
//差分数组
int main()
{
	int n, m, num[105], diff[105];
	cin >> n >> m;//数组中的元素个数，修改次数
	for (int i = 1; i <= n; i++)
	{
		cin >> num[i];
	}
	for (int i = 1; i <= n; i++)
	{
		diff[i] = num[i] - num[i - 1];//差分数组的创建 
	}
	for (int i = 0; i < m; i++)
	{
		int a, b, c;//a起始位，c是加减的值，b是结束的位
		cin >> a >> b >> c;
		diff[a] += c;
		diff[b + 1] -= c;
	}
	for (int i = 1; i <= n; i++)
	{
		num[i] = num[i - 1] + diff[i];//前缀和，还原出来值
	}
	for (int i = 1; i <= n; i++)
	{
		cout << num[i] << " ";
	}
	cout << endl;
	return 0;
}

 🔥大佬思路： 1109. 航班预订统计 – 力扣（LeetCode）

 👨‍🚀一个一个遍历bookings。然后去累加每一个booking[2]

 d

lass Solution {
public:
//二维数组 booksing[0,1,2]
		vector<int> Bookings(vector<vector<int>>& bookings, int n) {
				vector<int> res(n);
				for (auto &b : bookings) {
						for (int i = b[0] - 1; i < b[1]; i++) {
								res[i] += b[2];
						}
				}
				return res;
		}
};

差分法：思路：

1. 定义一个长度为n+1的整数向量res作为差分数组，初始化为全0。之所以长度为n+1，是因为bookings中的座位预订是从第i天到第j天（包含），所以差分数组的索引与天数之间有一个偏移量。

2. 遍历bookings数组中的每一个预订记录b，获取预订的起始天数l、结束天数r和座位数a。注意，因为差分数组的索引从0开始，而天数从1开始，所以需要将l和r减1。

3. 在差分数组res的l位置增加a，表示从第l天开始预订了a个座位；在r+1位置减去a，表示在第r+1天结束预订，座位数需要减少a。

4. 创建一个长度为n的整数向量fCount，用于存储每一天的航班座位预订总数。

5. 遍历res数组，从第1天开始累加差分数组的值到fCount数组中。如果当前是第1天（即i == 0），则直接将res[0]赋值给fCount[0]；否则，将前一天的总数fCount[i-1]加上res[i]，得到当前天的总数，并赋值给fCount[i]。

6. 返回fCount数组，即为每一天的航班座位预订总数。

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n + 1);
        int l = 0, r = 0, a = 0;
        for (auto & b : bookings) {
            l = b[0] - 1;
            r = b[1] - 1;
            a = b[2];
            res[l] += a;
            res[r + 1] -= a;
        }
        vector<int> fCount(n);

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                fCount[i] = res[0];
            }else {
                fCount[i] = fCount[i - 1] + res[i];
            }
        }
        return fCount;
    }
};

🎁🎁🎁今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，您的支持就是我前进的动力！