75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.Could you come up with a one-pass algorithm using only constant space? class Solution { public void sortColors(int[] nums) { if (nums == null || nums.length == 0) return; //left控制0最后出现的位置，right控制1最开始出现的位置（倒序） int left = 0; int right = nums.length - 1; int index = 0; while (index <= right) { if(nums[index] == 0) { swap(nums, index++, left++);//原地交换 } else if(nums[index] == 1) { index++;//不动 } else { swap(nums, index, right--);// } } } public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int j = n - 1; int k = m + n - 1; while (i >= 0 && j >= 0) { //nums1和2都是排过序的，从后向前放，最大的放在最后 nums1[k--] = nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--]; } while (j >= 0) { nums1[k--] = nums2[j--]; //i到极限，但是j还有剩余 } } }

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.Could you do it in-place with O(1) extra space?

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 2 * 10^4It’s guaranteed that nums[i] fits in a 32 bit-signed integer.k >= 0 // time O(n)，虽然三次翻转，但是没有累乘的操作 class Solution { public void rotate(int[] nums, int k) { //三次翻转 k %= nums.length; reverse(nums, 0, nums.length - 1);//整体翻转 reverse(nums, 0, k - 1);//翻转前k reverse(nums, k, nums.length - 1);//翻转剩下的n - k } public void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start++] = nums[end]; nums[end--] = temp; } } } // @lc code=end // class Solution { // public void rotate(int[] nums, int k) { // int[] temp = new int[nums.length]; // for (int i = 0; i < nums.length; i++) { // //如果K = 10，轮了一圈再往前轮三个，大于nums.length, 一开始i = 0, k = 3,把i当前的数给三这个位置 // //[1 ,2, 3, 4, 5, 6, 7]，因为0 + 3 % 7 = 3 // // 1 // temp[(i + k) % nums.length] = nums[i]; // } // //返回的是空，所以在原有的基础上操作，重新赋值 // //上面得到的结果存在temp里，要重新赋值 // for (int i = 0; i < nums.length; i++) { // nums[i] = temp[i]; // } // } // }

41. First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0] Output: 3

Example 2:

Input: [3,4,-1,1] Output: 2

Example 3:

Input: [7,8,9,11,12] Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

//Bucket Sort // [1 ,2, 0] index + 1 // [3, 4, -1, 1] 判断数是否大于0 // [1, 99, 3, 4]太大 // nums[nums[i] - 1] != nums[i] [3, 4, 1, 3] i = 0 nums[0] = 3, // nums[nums[i] - 1]就是当前的数应该放在的位置上 nums[0] = 3 - 1 = 2 -> nums[2]= -1 != nums[i]=3 class Solution { public int firstMissingPositive(int[] nums) { if (nums == null || nums.length == 0) return 1;//输出的是最小的正整数 for (int i = 0; i < nums.length; i++) { //这里是while,不是if [3, 1, 4, -1],if是单次 while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) { int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; } } for (int i = 0; i < nums.length; i++) { if(nums[i] != i + 1) { return i + 1; } } return nums.length + 1; } }