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

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

程序员文章站 2022-07-10 19:57:59
合并两个有序数组88. 合并两个有序数组题意:给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出:[1,2,2,3,5,6]思路1给个直观的,设置一个新的数组nums3,长度是nums1的长度,然后nums1和nums2遍历比较,小的放入。放完之后,将nums3数组赋值给nums1即可但是...

合并两个有序数组

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

相关标签: 数据结构与算法