欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

88 -合并排序数组

程序员文章站 2022-06-25 13:07:49
给定两个排序的整数数组nums1和nums2,将nums2合并为nums1作为一个排序的数组。 注意: 在nums1和nums2中初始化的元素数分别为m和n。 您可以假设nums1有足够的空间(大小大于或等于m + n)来保存nums2中的其他元素。 例: ......

给定两个排序的整数数组nums1nums2,将nums2合并nums1作为一个排序的数组。

注意:

  • nums1nums2初始化的元素分别mn
  • 您可以假设nums1有足够的空间(大小大于或等于m + n)来保存nums2中的其他元素

例:

输入:
nums1 = [1,2,3,0,0,0],m = 3
nums2 = [2,5,6],n = 3
输出:  [1,2,2,3,5,6]
 
解法1:
将nums2数组中的数据加在在nums1数据的后边。使用冒泡排序重新排序
public  void merge(int[] nums1, int m, int[] nums2, int n) {
            int i=m,j=0;
            while (i<m+n&&j<n)
            {
                nums1[i]=nums2[j];
                j++;
                i++;
            }
            for (int k=0;k<m+n-1;k++)
            {
                for (int p=0;p<m+n-k-1;p++)
                {
                  if (nums1[p]>nums1[p+1]) {
                  int temp=nums1[p];
                  nums1[p]=nums1[p+1];
                  nums1[p+1]=temp;
                  }
              }
          }
    }

解法二:
nums1[3,5,7,9,0,0,0];
nums2[1,4,8];
从两个数组的已有数据最末端(nums1数字9和nums数字8)开始对比,将大的数
置于nums1整个数组的最末端。然后将大的数所在的数组的索引-1.
当出现nums1数据的最首端(最小值)大于nums2的最大值时将nums2数组所有值放于nums1数组最前对应位置。
   public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while(i >= 0 && j >= 0) {
            nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }
        while(j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }