Chứa giải pháp leetcode trùng lặp javascript

Xin chào. Khi tôi tiếp tục tìm kiếm công việc của mình, tôi đang thực hành các câu hỏi về thuật toán của mình trên Leetcode. Vì vậy, tôi nghĩ rằng tôi sẽ viết blog về một số vấn đề về Leetcode khi tôi giải quyết chúng

Là một người tốt nghiệp Bootcamp, tôi không được thực hành nhiều về các thuật toán, vì vậy, việc nhận ra các mẫu và sai sót là một trải nghiệm rất thú vị và đôi khi khiến tôi nản lòng, tối ưu hóa mã của tôi để nhanh hơn (nhìn bạn Big-O), học cách phá vỡ . Tôi đã thực hành chúng bằng JavaScript

Vì tôi còn khá mới với các vấn đề về thuật toán, nên tôi đã bắt đầu với Bộ sưu tập dễ dàng các câu hỏi phỏng vấn hàng đầu của họ. Vì vậy, trong Chứa trùng lặp

Cho một mảng số nguyên nums, trả về true nếu bất kỳ giá trị nào xuất hiện ít nhất hai lần trong mảng và trả về false nếu mọi phần tử đều khác biệt

ví dụ

Input: nums = [1,2,3,1]
Output: trueInput: nums = [1,2,3,4]
Output: falseInput: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Đơn giản, nếu bất kỳ số nào trong mảng xuất hiện nhiều lần trong mảng, tôi cần trả về true. Bây giờ, tôi chắc chắn sẽ cần tìm ra cách để so sánh một số với các số khác. Ngoài ra, rất có thể tôi sẽ cần lặp qua mảng để tôi có quyền truy cập vào từng số để sau đó so sánh nó với các số khác

Đầu tiên, tôi nghĩ rằng tôi có thể lặp qua mảng và ở mỗi trường hợp, tôi lặp qua một vòng lặp khác của các số nguyên còn lại và so sánh chúng để xem có số nào bằng nhau không (===). Tuy nhiên, theo hiểu biết mới bắt đầu của tôi về Big-O, điều này sẽ mang lại cho tôi độ phức tạp thời gian không thuận lợi là O(n²)

Sau đó, tôi nghĩ rằng tôi có thể tạo một đối tượng và đếm xem một số trong mảng xuất hiện bao nhiêu lần. Bằng cách này, sau đó tôi có thể kiểm tra xem liệu có bất kỳ số nào có tổng số lớn hơn 1 không. Nếu vậy, tôi có thể trả lại true nếu không tôi sẽ trả lại false

var containsDuplicate = function(nums) {
    hash = {}
    let i = 0
    while (i < nums.length) {
        if (hash[nums[i]]) {
            hash[nums[i]] += 1
        } else {
            hash[nums[i]] = 1
        }
        i++
    }
    values = Object.values(hash)    for (let j = 0; j < values.length; j++){
        if (values[j] > 1) {
            return true
        }
    }
    return false
};

Và điều đó hiệu quả. giải quyết. Và độ phức tạp về thời gian sẽ là O(2n), nhanh hơn kế hoạch ban đầu của tôi. Tuy nhiên, tôi tự hỏi liệu tôi có thể dọn sạch thứ này và cải thiện một chút thời gian chạy Big-O của mình không?

Điều tôi nhận ra là tôi đã tạo một đối tượng khi tôi lặp qua mảng và tôi có thể trả về true ngay khi tôi tìm thấy bất kỳ số nào xuất hiện nhiều lần. Vì vậy, thay vì lặp qua toàn bộ mảng và sau đó kiểm tra các bản sao, tôi có thể làm điều đó cùng một lúc. Khi tôi lặp lại mảng, nếu nó không tồn tại trong đối tượng của tôi, thì tôi sẽ thêm nó vào. Nếu nó đã tồn tại trong đối tượng, thì tôi có thể trả lại true và kết thúc. Cuối cùng, nếu tôi chạy qua toàn bộ vòng lặp mà không nhấn vào câu lệnh return true, thì tôi sẽ trả về false

var containsDuplicate = function(nums) {
    hash = {}
    for (let i = 0; i < nums.length; i++) {
        if (hash[nums[i]]) {
            return true
        } else {
            hash[nums[i]] = 1
        }
    }
    return false
};

Bây giờ, điều đó có vẻ tốt hơn rất nhiều. Và nó chạy với độ phức tạp thời gian O(n) khá. Tôi tưởng tượng vẫn còn nhiều cách tốt hơn và nhanh hơn để giải quyết vấn đề này, vì vậy hãy để lại nhận xét cho tôi nếu mã của tôi có thể được cải thiện hoặc hướng dẫn tôi một cách mới để giải quyết vấn đề này (Tôi rất thích điều đó. )

Tôi hy vọng điều này sẽ giúp ích cho bạn nếu bạn gặp khó khăn khi giải quyết vấn đề này và tìm kiếm thêm các giải pháp Leetcode trong tương lai

Cho một mảng số nguyên nums, trả về true nếu bất kỳ giá trị nào xuất hiện ít nhất hai lần trong mảng và trả về false nếu mọi phần tử đều khác biệt

Dung dịch

Độ phức tạp về thời gian. O(n)
Độ phức tạp của không gian. O(n)

var containsDuplicate = function(nums) {
    const map = {}
    for(const num of nums) {
        // If we have seen this num before return true
        if(map[num]) return true
        map[num] = true
    }
    return false
};

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

Nhận xét hàng đầu (0)

Vương miện

Sắp xếp thảo luận

• Đã chọn Sắp xếp Tùy chọn Lên trên

  Những bình luận được bình chọn nhiều nhất và có liên quan sẽ được xếp đầu tiên

• Muộn nhất

  Những bình luận gần đây nhất sẽ là đầu tiên

• Cũ nhất

  Những bình luận cũ nhất sẽ được đầu tiên

Đặt mua

Người dùng cá nhân đáng tin cậy

Tạo mẫu

Mẫu cho phép bạn nhanh chóng trả lời Câu hỏi thường gặp hoặc lưu trữ đoạn mã để sử dụng lại

Gửi bản xem trước Bỏ qua

Quy tắc ứng xử • Báo cáo lạm dụng

Bạn có chắc chắn muốn ẩn bình luận này?

Làm cách nào để kiểm tra các mục trùng lặp trong JavaScript?

Làm cách nào để kiểm tra xem mảng có chứa số trùng lặp trong JavaScript không?

Làm cách nào để tránh JavaScript trùng lặp?

Làm cách nào để tìm các giá trị trùng lặp trong đối tượng bằng JavaScript?