作者：whisper

链接：http://proprogrammar.com:443/article/201

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

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

    颜色分类

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

此题中，我们使用整数 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] 中选取值大的。

    总结

    学习了排序，查找

亲爱的读者：有时间可以点赞评论一下