四大门户网站现状,python做网站感觉好费劲,四川省网站建设,学网站开发的软件有哪些系列专栏
双指针
模拟算法
分治思想 目录
1、题目链接
2、题目介绍
3、解法
解决方案选择
解题步骤
4、代码 1、题目链接
912. 排序数组 - 力扣#xff08;LeetCode#xff09;
2、题目介绍
给你一个整数数组 nums#xff0c;请你将该数组升序排列。
你必须在 …系列专栏
双指针
模拟算法
分治思想 目录
1、题目链接
2、题目介绍
3、解法
解决方案选择
解题步骤
4、代码 1、题目链接
912. 排序数组 - 力扣LeetCode
2、题目介绍
给你一个整数数组 nums请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题时间复杂度为 O(nlog(n))并且空间复杂度尽可能小。 示例 1 输入nums [5,2,3,1]
输出[1,2,3,5]示例 2 输入nums [5,1,1,2,0,0]
输出[0,0,1,1,2,5]提示 1 nums.length 5 * 104-5 * 104 nums[i] 5 * 104 3、解法 解决方案选择 为了满足时间复杂度的要求我们选择使用归并排序Merge Sort算法。归并排序是一种分而治之的算法它将数组分成两半递归地对它们进行排序然后将结果合并成一个有序数组。这个过程的时间复杂度为 O(nlog(n))因为它将问题分解成更小的子问题直到子问题的大小为1即已经排序然后将它们合并起来。 解题步骤 定义辅助函数 merge 函数负责将两个已排序的子数组合并成一个有序数组。它使用了一个临时数组 tmp 来存储合并过程中的元素以避免在原始数组上进行复杂的元素移动。mergeSort 函数递归地将数组分成更小的部分直到每个部分只包含一个元素自然是有序的然后调用 merge 函数将它们合并成有序数组。归并排序过程 拆分通过递归调用 mergeSort将数组不断拆分成更小的部分直到每个部分只包含一个元素。合并在递归返回的过程中使用 merge 函数将相邻的两个已排序的子数组合并成一个有序数组。空间复杂度 归并排序的空间复杂度主要由临时数组 tmp 决定其大小为 nums.size()因此空间复杂度为 O(n)。时间复杂度 归并排序的时间复杂度为 O(nlog(n))这主要是由于每次递归调用都将问题规模减半并且合并操作的时间复杂度为 O(n)。 4、代码 class Solution {
public://归并排序//void merge(vectorint nums, vectorint tmp, int left, int mid, int right){int lsort left, rsort mid 1;//两个需要进行合并区域的第一个元素下标int cur left;//遍历tmp数组的计数器while (lsort mid rsort right){if (nums[lsort] nums[rsort]){tmp[cur] nums[lsort];}else {tmp[cur] nums[rsort];}}//如果有剩余的数没有参与比较直接插入到tmp中while (lsort mid){tmp[cur] nums[lsort];}while (rsort right)tmp[cur] nums[rsort];while (left right){nums[left] tmp[left];left;}}//先拆分再合并void mergeSort(vectorint nums, vectorint tmp, int left, int right){if (left right){int mid (right left) / 2;mergeSort(nums, tmp, left, mid);mergeSort(nums, tmp, mid 1, right);merge(nums, tmp, left, mid, right);}}vectorint sortArray(vectorint nums) {vectorint tmp(nums.size());mergeSort(nums, tmp, 0, nums.size() - 1);return nums;}
}; 感谢阅读
