0%

Sorting And Array LEETCODE-100-DAY4

Posted on Edited on Valine:

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:

1
2
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?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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:

1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:

1
2
3
4
5
6
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:

1
2
3
4
5
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^4
  • It’s guaranteed that nums[i] fits in a 32 bit-signed integer.
  • k >= 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 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:

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

Example 2:

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

Example 3:

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

Note:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//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;
    }
}