Hướng dẫn leetcode remove duplicates from sorted array python - leetcode loại bỏ các bản sao khỏi python mảng được sắp xếp

Xin chào những người hạnh phúc 👋! Hãy cùng nhìn vào một vấn đề khác nhau ngày hôm nay.

• Loại bỏ các bản sao khỏi mảng được sắp xếp

Báo cáo vấn đề

Cho một mảng được sắp xếp nums, xóa các bản sao tại chỗ sao cho mỗi phần tử chỉ xuất hiện một lần và trả về độ dài mới.

Không phân bổ thêm không gian cho một mảng khác, bạn phải làm điều này bằng cách sửa đổi mảng đầu vào tại chỗ với bộ nhớ thêm O (1).O(1) extra memory.

Làm rõ: bối rối tại sao giá trị trả về là một số nguyên nhưng câu trả lời của bạn là một mảng? Lưu ý rằng mảng đầu vào được truyền vào theo tham chiếu, có nghĩa là sửa đổi cho mảng đầu vào cũng sẽ được người gọi biết.

Trong nội bộ bạn có thể nghĩ về điều này:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Constraints:

• 0 ≤ nums.length 3 × 104
• -104 ≤ nums[i] ≤ 104
• nums được sắp xếp theo thứ tự tăng dần.

Ví dụ

Ví dụ 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Ví dụ 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 length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Phân tích

Vấn đề này là thẳng như mô tả của nó là. Chúng tôi sẽ được cung cấp một mảng được sắp xếp có chứa các bản sao và chúng tôi chỉ cần giữ một thể hiện duy nhất của mỗi yếu tố. Ngoài ra, chúng ta cần cập nhật mảng tại chỗ, điều đó có nghĩa là chúng ta phải thực hiện tất cả các thao tác trong cùng một mảng mà không sử dụng bất kỳ cấu trúc dữ liệu nào.in-place which means we have to do all the manipulations in the same array without using any data structure.

Cuối cùng, chúng ta phải trả về chiều dài của mảng được cập nhật.

Cách tiếp cận

Một điều quan trọng trong câu hỏi là mảng được sắp xếp. Điều này có nghĩa là tất cả các yếu tố trùng lặp sẽ liền kề nhau. Ví dụ, trong mảng

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Chúng ta có thể sử dụng thuộc tính này của mảng được sắp xếp có chứa các bản sao để giải quyết câu hỏi này bằng các bước sau -

1. Kiểm tra xem hiện tại và phần tử tiếp theo có bằng nhau không.
2. Nếu có, chúng tôi sẽ bỏ qua yếu tố tiếp theo và sẽ tiếp tục thủ tục miễn là chúng tôi gặp phải các bản sao.
3. Nếu các phần tử không được sao chép, chúng ta sẽ đặt phần tử (khác nhau) tiếp theo bên cạnh phần tử hiện tại.

Độ phức tạp về thời gian

Chúng tôi đang quét mảng một lần, do đó độ phức tạp của thời gian sẽ là O (n).O(n).

Độ phức tạp không gian

Vì chúng tôi bị cấm sử dụng cấu trúc dữ liệu bên ngoài (và chúng tôi không sử dụng nó), độ phức tạp không gian sẽ là O (1).O(1).

Mã số

Java

public class RemoveDuplicatesFromSortedArray {

    public int removeDuplicates(int[] nums) {
        // Length of the updated array
        int count = 0;
        // Loop for all the elements in the array
        for (int i = 0; i < nums.length; i++) {
            // If the current element is equal to the next element, we skip
            if (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                continue;
            }
            // We will update the array in place
            nums[count] = nums[i];
            count++;
        }
        return count;
    }
}

Python

class RemoveDuplicatesFromSortedArray:
    def removeDuplicates(self, nums: List[int]) -> int:
        # Length of the update array
        count = 0
        # Loop for all the elements in the array
        for i in range(len(nums)):
            # If the current element is equal to the next element, we skip
            if i < len(nums) - 2 and nums[i] == nums[i + 1]:
                continue
            # We will update the array in place
            nums[count] = nums[i]
            count += 1
        return count

JavaScript

var removeDuplicates = function (nums) {
    // Length of the updated array
    let count = 0;
    // Loop for all the elements in the array
    for (let i = 0; i < nums.length; i++) {
        // If the current element is equal to the next element, we skip
        if (i < nums.length - 1 && nums[i] == nums[i + 1]) {
            continue;
        }
        // We will update the array in place
        nums[count] = nums[i];
        count++;
    }
    return count;
};

Kotlin

class RemoveDuplicatesFromSortedArray {

    fun removeDuplicates(nums: IntArray): Int {
        // Length of the updated array
        var count = 0
        // Loop for all the elements in the array
        for (i in nums.indices) {
            // If the current element is equal to the next element, we skip
            if (i < nums.size - 1 && nums[i] == nums[i + 1]) {
                continue
            }
            // We will update the array in place
            nums[count] = nums[i]
            count++
        }
        return count
    }
}

Hoàn thành mã

• Java
• Python
• JavaScript
• Kotlin

Hoàn thành mã

Sự kết luận

Xin chúc mừng! Trong bài đăng này, chúng tôi đã giải quyết một vấn đề dễ dàng từ LeetCode liên quan đến Array.

Tôi hy vọng bạn thích bài viết này. Hãy chia sẻ suy nghĩ của bạn về điều này.

Bạn có thể tìm thấy mã nguồn đầy đủ trên kho lưu trữ GitHub của tôi. Nếu bạn thích những gì bạn học, hãy thoải mái và sao.

Làm cách nào để loại bỏ các bản sao khỏi một mảng được sắp xếp trong Python?

Làm cách nào để loại bỏ các bản sao khỏi một mảng tại chỗ?

Làm thế nào để bạn tìm và loại bỏ các bản sao khỏi một danh sách trong Python?

Làm thế nào để bạn loại bỏ các bản sao khỏi một bộ?