数据结构与算法---数组、排序---合并两个有序数组、 颜色分类

合并两个有序数组

88. 合并两个有序数组

题意：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出：[1,2,2,3,5,6]

---

思路1 待验证

给个直观的，设置一个新的数组nums3，长度是nums1的长度，然后nums1和nums2遍历比较，小的放入。放完之后，将nums3数组赋值给nums1即可

但是，如果要求空间复杂度为O(1)呢？
也就是不准建立新的数组

思路2 待验证

那就只能将比较的结果一个一个放入nums1中。
是从前一个一个比较？还是从后一个一个比较？

假设是从前往后比，那么，找出的比较大的元素放置在哪？
明确的是不应该放置在0位置上
那就是，如果nums1[i] > nums2[j] ，两者交换位置，i++;
如果nums1[i] <= nums2[j]，j++;

貌似也行

如果是从后往前比较呢？

思路3

设置nums1需要比较的位置为nums1Compare
设置nums1需要插入的位置为nums1Insert
设置nums2需要比较的位置为nums2Compare

如果nums2提前结束，则结束比较，nums1不需要动

如果上面的nums1提前结束，则将nums2赋值到nums1上即可

package 排序_数组;

public class _88_合并两个有序数组 {
	
	public static void main(String[] args)
	{
		int[] nums1 = {2, 0};
		int[] nums2 = {1};
		merge(nums1, 1, nums2, 1);
		
		for (int i = 0; i < nums1.length; i++) {
			System.out.print(nums1[i] + " ");
		}
	}
	
	public static void merge(int[] nums1, int m, int[] nums2, int n) {
		//从后往前走
		//需要三个指针
		
		//指向要插入的地方
		int nums1Insert = nums1.length - 1;
		//指向要比较的nums1元素
		int nums1Compare = m - 1;
		//指向要比较的nums2元素
		int nums2Compare = n - 1;
		
		//不需要nums1Compare >= 0，因为nums2Compare小于0，说明nums2比较完了，剩余的nums1不用动了
		//而nums1Compare < 0，还得将nums2的数据赋值
		while(nums2Compare >= 0)
		{
			if (nums1Compare < 0 || nums1[nums1Compare] < nums2[nums2Compare]) {
				nums1[nums1Insert] = nums2[nums2Compare];
				nums1Insert--;
				nums2Compare--;
			}else {
				nums1[nums1Insert] = nums1[nums1Compare];
				nums1Insert--;
				nums1Compare--;
			}
		}
    }
}

---

颜色分类

75.颜色分类
题目：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

思路

注意，原地，指的是空间复杂度为O(1)

一般来说，扫描一遍数组就可以解题的，需要借助多个指针。
双指针、三指针

由于题目只有0、1、2三种数字类型
那么，顺序扫描：
如果是0，则放在最前面；
如果是2，则放在最后面；
如果是1，则不动；

假设有一个扫描指针，currentPoint
如果扫描的是0，则需要放在前面的位置，也就是还需要有一个指针指向0需要插入的位置leftPoint
如果扫描的是2，则需要放在后面的位置，也就是还需要有一个指针指向2需要插入的位置rightPoint

如果是0，则currentPoint指向的数值 与 leftPoint指向的数值交换，然后currentPoint++、leftPoint++；
如果是2，则currentPoint指向的数值 与 rightPoint指向的数值交换，rightPoint–，然后再次对currentPoint指向的值进行判断
如果是1，则currentPoint++；

什么时候截止呢？
rightPoint < currentPoint的时候

class Solution {
    public void sortColors(int[] nums) {

        /**
        如果是0，则currentPoint指向的数值 与 leftPoint指向的数值交换，然后currentPoint++、leftPoint++；
        如果是2，则currentPoint指向的数值 与 rightPoint指向的数值交换，rightPoint--，然后再次对currentPoint指向的值进行判断
        如果是1，则currentPoint++；
        */
        int leftPoint = 0;
        int rightPoint = nums.length - 1;
        int currentPoint = 0;
        while(rightPoint >= currentPoint){
            if(nums[currentPoint] == 0){
                int temp = nums[currentPoint];
                nums[currentPoint] = nums[leftPoint];
                nums[leftPoint] = temp;
                currentPoint++;
                leftPoint++;
            }else if(nums[currentPoint] == 2){
                int temp = nums[currentPoint];
                nums[currentPoint] = nums[rightPoint];
                nums[rightPoint] = temp;
                rightPoint--;
            }else if(nums[currentPoint] == 1){
                currentPoint++;
            }
        }
    }
}

本文地址：https://blog.csdn.net/IOSSHAN/article/details/109464432