合并两个有序数组

题目详情：

  1. 给你两个按非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
  2. 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
  3. 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例

  1. #示例1 
  2. 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
  3. 输出：[1,2,2,3,5,6]
  4. 解释：需要合并 [1,2,3] 和 [2,5,6] 。
  5. 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
  7. #示例2
  8. 输入：nums1 = [1], m = 1, nums2 = [], n = 0
  9. 输出：[1]
  10. 解释：需要合并 [1] 和 [] 。
  11. 合并结果是 [1] 。
  13. #示例3
  14. 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
  15. 输出：[1]
  16. 解释：需要合并的数组是 [] 和 [1] 。
  17. 合并结果是 [1] 。
  18. 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
  20. #提示
  21. nums1.length == m + n
  22. nums2.length == n
  23. 0 <= m, n <= 200
  24. 1 <= m + n <= 200
  25. -109 <= nums1[i], nums2[j] <= 109

解题思路1

有很多种，我只理解和记住我写的，其他的等2刷我在去弄懂，所以看的时候，可以点击上方的链接进行看

  1. 通过题目和示例来看，一共有2个数组且这2个数组为有序数组；
  2. 需要把这2个数组合并到到一起，合并完为有序的数组，所以直接把数组2放进数组1里面，然后进行排序即可
  3. 如何将数组2如何合并到数组1为关键
    1. 数组1的长度为 m+n；
    2. 数组2的长度为 n；
    3. 把数组2直接放到数组1的后面即可 ```java // m = nums1.length 元素数目 // n = nums2.length 元素数目 for(int i = 0; i!=n ; i++){ nums1[m+i]= nums2[i]; }
  2. 4. 排序数组
  3. ```java
  4. Arrays.sort(nums1);

具体代码

  1. class test1{
  2.     public void merge(int [] nums1, int m,int []nums2,int n){
  3.         for(int i = 0 ; i !+n ;i++){
  4.             nums1[m+i] = nums2[i];
  5.         }
  6.         Arrays.sort(nums1);
  7.     }
  8. }

解题思路2

  1. 有个官方的api，System.arraycopy，直接copy数组2到数组1里面；
  2. 具体System.arraycopy的使用，可以记一下，以后在其他地方用起来也方便
    • src参数：源数组
    • srcPos参数：从src数组的第几个元素开始赋值
    • dest参数：目标数组
    • destPos参数：指定从dest数组的第几个元素开始。
    • length参数：指定从src数组拿几个元素来赋值到dest数组
      1. System.arraycopy(nums2,0,nums1,m+1,n);
      2. Arrays.sort(nums1);

      多数元素

      题目详情：

      1. 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
      2. 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
      示例 ```java

      示例1

      输入：[3,2,3] 输出：3

示例2

输入：[2,2,1,1,1,2,2] 输出：2

  1. <a name="OMgLq"></a>
  2. #### 解题思路
  4. 1. 因为是排序题，先将无序数组进行排序
  5. ```java
  6. Arrays.sort(nums1);
  7. // 输出之后示例1的数组是[2,3,3] 示例2的数组是 [1,1,1,2,2,2,2,3]
  1. 根据实际示例输出的结果，示例1为3，示例2为2，多数元素是大于n/2次数，也就是一半以上都是多数元素，所以length/2 肯定是排序之后的多数元素
    1. nums1[nums1.length/2]

    具体的代码

    1. class test{
    2.  public static void main(String[] args) {
    3.      int [] nums1 = {2,2,1,1,1,2,1,2};
    4.      Arrays.sort(nums1);
    5.      return nums1[nums.length/2];
    6.  }
    7. }

    其他：摩尔投票法

    算法原理：每次从数组中找出一对不同的元素，将它们从数组中删除，直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。

我理解了解题思路，自己并没有写。等我再看看python在过来写；