LeetCode 之 Merge Sorted Array(排序)

【问题描述】

Given two sorted integer arraysnums1andnums2, mergenums2intonums1as one sorted array.

Note:You may assume thatnums1has enough space (size that is greater or equal tom+n) to hold additional elements fromnums2. The number of elements initialized innums1andnums2aremandnrespectively.

1.【基础知识】

归并排序思想

常见的排序主要有两种,一种是先把待排序的序列一次分割,使子序列的长度减小至1,然后,再合并。另外一种是把待排序两两分组排序然后合并。

堆排序思想

详见:数据结构基础 排序 之 二叉堆实现堆排序

详址:

2.【屌丝源码】

未能给出完整实现!

class Solution {public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {if (nums1.empty()) {nums1 = nums2;return;}if (nums2.empty()) return ;qkst(nums1);qkst(nums2);vector<int> myvec;int k=0,j=0;for(int i=0;i<nums2.size()+nums1.size();i++){// 一方耗尽怎么办if(k>=nums2.size()){fornums1 = myvec;return ;}if(j>=nums1.size()){fornums1 = myvec;return ;}if(nums1[j]>=nums2[k]){myvec.push_back(nums2[k]);k++;}else{myvec.push_back(nums1[j]);++j;}}nums1 = myvec;return ;}int pivot(int low,int high,vector<int> &vec){return 0;}void qkst(vector<int> &vec){}};3.【AC源码】class Solution {public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int ia = m – 1, ib = n – 1, icur = m + n – 1;while(ia >= 0 && ib >= 0) {nums1[icur–] = nums1[ia] >= nums2[ib] ? nums1[ia–] : nums2[ib–];}while(ib >= 0) {nums1[icur–] = nums2[ib–];}}};4.【算法思想】

1)遇到插入操作,最好用空间复杂度来解决时间复杂度问题;2)插入操作,其实操作为尾操作比为首操作的要简单、直接;

3)简单问题复杂化是最不值得的,目标为导向,,干出来了,有了结果再说别的!

4)卡壳地方:a.审题;b.概念混淆;c.结果导向不明。

版权声明:本文为博主原创文章,未经博主允许不得转载。

我躺下来,以一张报纸当枕头。高高在我上方的,

LeetCode 之 Merge Sorted Array(排序)

相关文章:

你感兴趣的文章:

标签云: