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.

1, chúng ta thấy tất cả các yếu tố trùng lặp liền kề nhau.the array is sorted. This means that all the duplicate elements will be adjacent to each other. For e.g., in the array

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.

1, we see all the duplicate elements are adjacent to each other.

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