目录
- 题目
- 解法
- 初始数组
- 1. 分解阶段
- 2. 合并阶段
- 结果
- 为什么要创建长整型
- ll mid = l + ((r - l) >> 1);其中的>>是什么意思
题目
给你一个整数数组 nums,请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n)),并且空间复杂度尽可能小。
解法
typedef long long ll;
const int N = 1e5 + 1;
class Solution {ll help[N];void merge(vector<int>& nums, ll l, ll r) {//1、将数组排序if (l >= r) return;ll mid = l + ((r - l) >> 1);ll i = l, j = mid + 1, t = l;while (i <= mid && j <= r) {help[t++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];}//2、将左半区域剩余元素排序while (i <= mid) {help[t++] = nums[i++];}//3、将右半区域剩余元素排序while (j <= r) {help[t++] = nums[j++];}//4、复制数组for (int i = l; i <= r; i++) {nums[i] = help[i];}return;}void mergeSort(vector<int>& nums, ll l, ll r) {if (l < r) {ll mid = l + ((r - l) >> 1);//左边区域mergeSort(nums, l, mid);//右边区域mergeSort(nums, mid + 1, r);//合并左右区域merge(nums, l, r);}}public:vector<int> sortArray(vector<int>& nums) {int n = nums.size();mergeSort(nums, 0, n - 1);return nums;}
};
好的,下面我将详细展示使用归并排序的过程,以数组 nums = {38, 27, 43, 3, 9, 82, 10}
为例。
初始数组
nums = {38, 27, 43, 3, 9, 82, 10}
1. 分解阶段
归并排序首先将数组分解成子数组,直到每个子数组只包含一个元素。
-
初始分解:
{38, 27, 43, 3, 9, 82, 10}
-
继续分解:
{38, 27, 43} {3, 9, 82, 10}
-
再次分解:
{38} {27, 43} {3, 9} {82, 10}
-
继续分解:
{38} {27} {43} {3} {9} {82} {10}
2. 合并阶段
接下来开始合并和排序:
-
合并
{27}
和{43}
:{27, 43}
-
合并
{27, 43}
和{38}
:{27, 38, 43}
-
合并
{3}
和{9}
:{3, 9}
-
合并
{82}
和{10}
:{10, 82}
-
合并
{3, 9}
和{10, 82}
:{3, 9, 10, 82}
-
最后合并
{27, 38, 43}
和{3, 9, 10, 82}
:{3, 9, 10, 27, 38, 43, 82}
结果
经过归并排序后,数组 nums
最终变为:
nums = {3, 9, 10, 27, 38, 43, 82}
为什么要创建长整型
typedef long long ll;:这行代码为 long long 类型创建了一个别名 ll。这样,在后续的代码中,你可以使用 ll 来代替 long long,使代码更简洁易读。
const int N = 1e5 + 1;:这行代码定义了一个常量 N,其值为 100001。通常在算法中,N 可能用于表示数组的最大大小或某种限制,以确保在使用时不会越界。
在 C++ 中,创建 long long
类型的原因主要是为了处理更大的整数范围。long long
通常用于存储可能超出 int
范围的数值,特别是在涉及到大数运算、数组索引、计数或求和时。以下是一些具体的原因:
-
数值范围:
int
的范围通常是 -2,147,483,648 到 2,147,483,647,而long long
的范围可以达到 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807,适合处理更大的数值。 -
避免溢出:在进行大量累加、乘法等运算时,如果使用
int
,可能会出现溢出错误。使用long long
可以降低这种风险。 -
算法需要:在一些算法(如动态规划、图算法等)中,可能需要处理大量数据或计算结果,使用
long long
确保结果不会溢出。
因此,在需要处理较大整数的情况下,使用 long long
是一种常见的做法。
ll mid = l + ((r - l) >> 1);其中的>>是什么意思
“”>> 是位移运算符,表示右移操作。在这个表达式中,(r - l) >> 1 相当于将 (r - l) 的值除以 2,用于计算中间值 mid,以提高效率。