数组与双指针

• 26. Remove Duplicates from Sorted Array
  • 思路
  • C++解法
  • Java解法
  • Python3解法
  • Go解法
• 27. Remove Element
  • 思路
  • C++解法
  • Java解法
  • Python3解法
  • Go解法
• 88. Merge Sorted Array
  • 思路
  • C++解法
  • Java解法
  • Python3解法
  • Go解法
• 977. Squares of a Sorted Array
  • 思路
  • C++解法
  • Java解法
  • Python3解法
  • Go解法

26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Example 1:

**Input:** nums = [1,1,2]
**Output:** 2, nums = [1,2,_]
**Explanation:** Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

**Input:** nums = [0,0,1,1,1,2,2,3,3,4]
**Output:** 5, nums = [0,1,2,3,4,_,_,_,_,_]
**Explanation:** Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

思路

仿照移除元素，使用快慢指针移除重复元素

C++解法

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int j = 1;
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] != nums[i - 1]){
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
};

Java解法

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

Python3解法

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[j] = nums[i]
                j += 1
        return j

Go解法

func removeDuplicates(nums []int) int {
    slow := 1
    for fast := 1; fast < len(nums); fast = fast + 1{
        if nums[fast] != nums[fast - 1]{
            nums[slow] = nums[fast]
            slow = slow + 1
        }
    }
    return slow
}

注意：这里LeetCode背后的数组格式是左闭右开的，即返回数组的索引范围是[0, slow-1]

27. Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Example 1:

**Input:** nums = [3,2,2,3], val = 3
**Output:** 2, nums = [2,2,_,_]
**Explanation:** Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

**Input:** nums = [0,1,2,2,3,0,4,2], val = 2
**Output:** 5, nums = [0,1,4,0,3,_,_,_]
**Explanation:** Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

思路

双指针（快慢指针）

C++解法

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        int slow = 0;
        for(int fast = 0; fast < size; fast++)
        {
            if(nums[fast] != val)
            {
                nums[slow++] = nums[fast];
            }  
        }
        return slow;
    }
    
};

Java解法

class Solution {
    public int removeElement(int[] nums, int val) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }
}

Python3解法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        index = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[index] = nums[i]
                index += 1
        return index

Go解法

func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast = fast + 1{
        if nums[fast] != val{
            nums[slow] = nums[fast]
            slow = slow + 1
        }
    }
    return slow
}

另一种解法：

func removeElement(nums []int, val int) int {
    i := 0
    for _, v := range nums {
        if v != val {
            nums[i] = v
            i++
        }
    }
    return i
}

88. Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

**Input:** nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
**Output:** [1,2,2,3,5,6]
**Explanation:** The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

**Input:** nums1 = [1], m = 1, nums2 = [], n = 0
**Output:** [1]
**Explanation:** The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

**Input:** nums1 = [0], m = 0, nums2 = [1], n = 1
**Output:** [1]
**Explanation:** The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

思路

基本解法：复制nums2的内容到nums1中，然后排序，此时Time Complexity为$O((M+N)Log(M+N))$

C++解法

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i = m, j = 0; i< nums1.size() && j < n; i++, j++){
            nums1[i] = nums2[j];
        }
        sort(nums1.begin(), nums1.end());
    }
};

Java解法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int j = 0, i = m; j < n; j++) {
            nums1[i] = nums2[j];
            i++;
        }
        Arrays.sort(nums1);
    }
}

Python3解法

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        for j in range(n):
            nums1[m + j] = nums2[j]
        nums1.sort()
        

Go解法

func merge(nums1 []int, m int, nums2 []int, n int)  {
    for i, j := m, 0; i < len(nums1) && j < n; i, j = i + 1, j + 1{
        nums1[i] = nums2[j]
    }
    sort.Ints(nums1)
}

977. Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

**Input:** nums = [-4,-1,0,3,10]
**Output:** [0,1,9,16,100]
**Explanation:** After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

**Input:** nums = [-7,-3,2,3,11]
**Output:** [4,9,9,49,121]

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

思路

方法一：原地平方然后排序

方法二：双指针（左右指针）

C++解法

方法一：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            nums[i] *= nums[i];
        }
        sort(nums.begin(), nums.end()); 
        return nums;
    }
};

方法二：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> results(nums.size());
        int k = nums.size() - 1;
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right)
        {
            if(nums[left] * nums[left] > nums[right] * nums[right])
            {
                results[k--] = nums[left] * nums[left];
                left++;
            }
            else
            {
                results[k--] = nums[right] * nums[right];
                right--;
            }
        }
        return results;
    }
};

Java解法

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] result = new int[nums.length];
        int index = nums.length - 1;
        while(left <= right){
            if(Math.abs(nums[left]) > Math.abs(nums[right])){
                result[index--] = nums[left] * nums[left];
                left++;
            }else{
                result[index--] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

Python3解法

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        start, end = 0, n - 1
        for i in range(n - 1, -1, -1):
            if abs(nums[start]) >= abs(nums[end]):
                ans[i] = nums[start] * nums[start]
                start += 1
            else:
                ans[i] = nums[end] * nums[end]
                end -= 1
        return ans

Go解法

func sortedSquares(nums []int) []int {
    n := len(nums)
    results := make([]int, n)
    k := n-1
    left, right := 0, n - 1

    for left <= right {
        if nums[left]*nums[left] > nums[right]*nums[right] {  
            results[k] = nums[left] * nums[left]  
            left++  
        } else {  
            results[k] = nums[right] * nums[right]  
            right--  
        }  
        k--  
    }
    return results;
}