通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode探索之数组类算法学习 运用基础算法思想

4808人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode

作者:因情语写

链接:https://www.qingyu.blue/article/201

声明:请尊重原作者的劳动,如需转载请注明出处


    典型的排序算法思想、二分查找思想在解 LeetCode 题目时很有用。


    颜色分类

给定一个包含红色、白色和蓝色,一共 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

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

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

示例:

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

进阶:

  • 一个直观的解决方案是使用计数排序的两趟扫描算法。
    首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
  • 你能想出一个仅使用常数空间的一趟扫描算法吗? 

 

     想法:计算出每种颜色的数量,重写当前数组

// 想法:计算出每种颜色的数量,重写当前数组
    public void sortColors(int[] nums) {
        if(nums == null || nums.length == 0)
        {
            return;
        }
        
        int c0 = 0;
        int c1 = 0;
        for(int i = 0; i < nums.length; i++)
        {
            if(nums[i] == 0)
            {
                c0++;
            }
            if(nums[i] == 1)
            {
                c1++;
            }
        }
        
        for(int i = 0; i < nums.length; i++)
        {
            if(i < c0)
            {
                nums[i] = 0;
            }
            else if(i < c0 + c1)
            {
                nums[i] = 1;
            }
            else
            {
                nums[i] = 2;
            }
        }
    }

    用到了两个变量,比要求的多用了一个变量,看一下更好的算法

public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        //定义一个当前指针
        int curr = 0;
        //定义计算0的个数的指针
        int p0 = 0;
        //定义计算2的个数的指针
        int p2 = nums.length - 1;
        int temp;
        while (curr <= p2) {
            if (nums[curr] == 0) {
                //与p0交换
                temp = nums[p0];
                nums[p0] = nums[curr];
                nums[curr] = temp;
                p0++;
                curr++;
            } else if (nums[curr] == 2) {
                //与p2交换
                temp = nums[p2];
                nums[p2] = nums[curr];
                nums[curr] = temp;
                p2--;
            } else {
                curr++;
            }
        }
    }

    这个算法竟用到了4个变量,但优点就是一个循环就全部搞定,我的做法算是条理比较清晰吧

    解题思路

    基数排序法

    可以采用基数排序法的思想,用一个数组记录下 0,1,2 的次数,后重排,这个算法对数组进行了两次遍历,其实有一种只进行一次遍历的方法。

    三路快速排序方法

    设置三个 lt, gt, i 定义:nums[0...lt] == 0,nums[lt+1...i-1] = 1,nums[gt...n-1] == 2,遍历一遍改数列保持这个定义。


    数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

    说明:我先对数组进行了一次排序(最熟悉的是冒泡排序),再返回倒数第k个数

 

public int findKthLargest(int[] nums, int k) {
        nums = bubbleSort(nums, nums.length);
        
        return nums[nums.length - k];
    }
    
    private int[] bubbleSort(int[] nums, int n)
    {
        int temp;
        for(int i = 0; i < n - 1; i++)
            for(int j = 0; j < n - 1 - i; j++)
            {
                if(nums[j] > nums[j+1])
                {
                    temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        
        return nums;
    }

    这个方法应该说是非常不好了,效率极低,看一个好的算法

/**
	 * 在[left,right)区间内随便猜选择一个数a(比如选择nums[k-1]),猜他是数组中的第k大数,把所有大
	 * 于它的数字放在它的左边,所有小于它的数字放在它的右边,这个放置的过程为了减少数组的移动,处理的有点
	 * 像快速排序的一次遍历(同时找到“a左边比a小的数字b”和“a右边比a大的数字c”,将b,c交换。重复上述过
	 * 程就能将比a大的数字全部转移到a的左边,比a小的数字全部转移到a的右边)。通过这样的处理就知道a是数
	 * 组中第几大的数字(比如通过这次处理发现a是数组中第m大的数字)。如果m=k,那么第k大的数字就是a;如果
	 * m<k,就对a右边的数字进行同样的处理;如果m>k,就对m左边的数字进行处理。
	 *
	 * 时间复杂度:
	 * 理论上遍历数组两遍就能得到结果(n+n/2+n/4+n/8....n是数组长度),故为O(n)
	 * 最坏情况,每次judgeNum都猜得不准。两次迭代之间,数组的长度只减少了一位。(n+n-1+n-2....)故为O(n^2)
	 * 最好情况,第一次猜就中了,为O(n)
	 * 
	 * 空间复杂度:
	 * O(1)
	 * */
	public int findKthLargest(int[] nums, int k) {
		//[left,right]为处理区间
		int left = 0;
		int right = nums.length - 1;

		//左边的指针lPoint,右边的指针rPoint,类似快速排序时使用的两个左右指针
		int lPoint = left;
		int rPoint = right;
		int judgePoint = left;

		//可以极大限度的缩短时间的一个步骤,即预测第k大数字出现在数组的第k-1位
		//如果这个数组越是按照从大到小排序的话这个预测就越准确,如此预测后面循环的次数就会减少
		swap(nums,judgePoint,k-1);

		//数组中的数字就是和这个judgeNum比较大小
		int judgeNum = nums[judgePoint];
		do {
			//寻找比judgeNum大的数字
			while (rPoint > lPoint && nums[rPoint] <= judgeNum) {
				rPoint--;
			}
			//寻找比judgeNum小的数字
			while (rPoint > lPoint && nums[lPoint] >= judgeNum) {
				lPoint++;
			}
			//此次迭代结束
			if (lPoint == rPoint) {
				swap(nums, judgePoint, lPoint);
				if (lPoint < k - 1) {
					left = lPoint + 1;
					lPoint = left;
					rPoint = right;
					judgePoint = left;
					swap(nums,judgePoint,k-1);
					judgeNum = nums[judgePoint];
				} else if (lPoint > k - 1) {
					right = lPoint - 1;
					lPoint = left;
					rPoint = right;
					swap(nums,judgePoint,k-1);
					judgeNum = nums[judgePoint];
				} else {
					break;
				}
			//交换两个数字
			} else {
				swap(nums, lPoint, rPoint);
			}
		} while (true);
		return nums[lPoint];
	}

	private void swap(int[] nums, int lPoint, int rPoint) {
		int temp = nums[lPoint];
		nums[lPoint] = nums[rPoint];
		nums[rPoint] = temp;
	}

    这个方法有点难以理解,不过还好注释比较多,我再解释一下,就是假设数组的第k个数是第k大的,在k的左边是不小于第k个数的,在k的右边是不大于第k个数的,左右双端向中间逼近,直到两端相等,如果中间出现左边小于第k个数而右边大于第k个数,则交换两个数以保证左边大右边小,等两边排好时(左右端相等)看左(右)指针的位置,如果正好是k个数的位置,那么结束返回第k个数,如果偏左(指针位置小于k这个数位置),那么说明数选大了,要的数在右边(小的一边),那么缩小范围到右边,从右边选一个数,重复这个过程,如果偏右(指针位置大于k这个数位置),那么说明数选小了,要的数在左边(大的一边),那么缩小范围到左边,从左边选一个数,重复这个过程,因为过程中会不断缩小范围到左边或者右边,所以最后一定会左右两边等于第k个数的位置,返回这个数即可,不太懂的可以大致按我说的思路想一想,swap的目的有两个,将第k个数换到最左端,交换大小位置不正确的两个数。

    解题思路

    说明:官方给的解题思路是用快速排序的方法,也就比我的冒泡好一点,还是上面给的方法比较好。

    利用快速排序的思想,从数组 S 中随机找出一个元素 X,把数组分为两部分 Sa 和 Sb。Sa 中的元素大于等于 X,Sb 中元素小于 X。这时有两种情况:

  • Sa 中元素的个数小于 k,则 Sb 中的第 k-|Sa| 个元素即为第k大数;
  • Sa 中元素的个数大于等于 k,则返回 Sa 中的第 k 大数。时间复杂度近似为 O(n)

 


    合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n
  • 你可以假设 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]

 

    思路:使用额外的一个数组存nums1中的有效元素,再同nums2中的元素一起存到nums1中,存时同时从两个数组中取,把较小的存入nums1

// 思路:使用额外的一个数组存nums1中的有效元素,再同nums2中的元素一起存到nums1中,存时同时从两个数组中取,把较小的存入nums1
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums3 = new int[m];
        System.arraycopy(nums1, 0, nums3, 0, m);
        int m1 = 0;
        int m2 = 0;
        int m3 = 0;
        
        while(m2 < n && m3 < m)
        {
            if(nums2[m2] < nums3[m3])
            {
                nums1[m1++] = nums2[m2];
                m2++;
            }
            else
            {
                nums1[m1++] = nums3[m3];
                m3++;
            }
        }
        
        while(m2 < n)
        {
            nums1[m1++] = nums2[m2++];
        }
        
        while(m3 < m)
        {
            nums1[m1++] = nums3[m3++];
        }
    }

     这里用的是合并两个有序数组成一个有序数组的常规方法,算是比较好的方法了,再看一个效率更高的方法

public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m - 1; i >= 0; i--) {
            nums1[n + i] = nums1[i];
        }
        int i = 0;
        int j = 0;
        int index = 0;
        while (i < m && j < n) {
            if (nums1[n + i] < nums2[j]) {
                nums1[index] = nums1[n + i];
                i++;
            } else {
                nums1[index] = nums2[j];
                j++;
            }
            index++;
        }
        if (i >= m) {
            while (j < n) {
                nums1[index] = nums2[j];
                index++;
                j++;
            }
        }
        // for (int t : nums1) {
        // System.out.println(t);
        // }
    }

    这个算法的优点是不需要用额外的数组,而且不用处理nums1中可能多出的元素

    解题思路

    常规解题思路

    其实这道题就是归并排序 partition 的过程(将两个有序的数列合并成一个有序数列),直观的思路是新建一个新的数列,遍历 nums1 和 nums2 这两个数列,将新建的数列有序后又赋值给 nums1 后返回。其实还有一种方法不需要开辟新的空间。

    尾插法

    由于 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素,所以从 k=m+n-1 开始,分别遍历 nums1[m...0] 和 nums2[n...0] 中选取值大的。


    总结

    学习了排序,查找


亲爱的读者:如果你喜欢文章的话,不妨点赞评论支持作者一下吧


点赞(0) 打赏

全部评论

还没有评论!