Làm thế nào để bạn tìm thấy các số trùng lặp trong một mảng nếu nó chứa nhiều số trùng lặp python?

Trước khi xem các giải pháp, hãy nói một chút về vấn đề. Chúng tôi nhận được một mảng của phần tử n + 1 với các số nguyên từ 1 đến n

Ví dụ, với một mảng gồm 5 số nguyên, nó ngụ ý rằng mỗi số nguyên sẽ có giá trị từ 1 đến 4 [bao gồm]. Điều này có nghĩa là sẽ tự động có ít nhất một bản sao

Ngoại lệ duy nhất là với một mảng có kích thước 1. Đây là trường hợp duy nhất mà chúng ta nên trả về -1

Lực lượng vũ phu

Giải pháp vũ phu là thực hiện hai vòng lặp lồng nhau theo cách này

for i = 0; i < size[a]; i++ {
  for j = i+1; j < size[a]; j++ {
    if[a[i] == a[j]] return a[i]
  }
}

Độ phức tạp thời gian O[n²] và độ phức tạp không gian O[1]

Đếm số lần lặp

Một giải pháp khác là có cấu trúc dữ liệu để đếm số lần lặp của mỗi số nguyên. Giải pháp này có thể được thực hiện với một mảng hoặc bảng băm

Một triển khai trong Java

Giá trị của chỉ số i đại diện cho số lần lặp lại của i+1

Giải pháp này là thời gian O[n] nhưng không gian O[n] vì chúng ta cần một cấu trúc bổ sung

Mảng được sắp xếp

Nếu chúng ta áp dụng kỹ thuật đơn giản hóa, chúng ta có thể thử tìm một giải pháp với một mảng được sắp xếp

Trong trường hợp này, chúng ta chỉ cần so sánh từng phần tử với hàng xóm bên phải của nó

Trong Java

O[1] trong không gian nhưng O[n log[n]] trong thời gian vì chúng tôi cần sắp xếp bộ sưu tập trước

Tổng các phần tử

Một hướng chúng ta có thể nghĩ đến là tính tổng các phần tử của mảng và so sánh nó với 1 + 2 + … + n

Hãy xem một ví dụ

Input: [1, 4, 3, 3, 2, 5]
Sum = 18As in this example, we have n = 5:
Sum of 1 to 5 = 1 + 2 + 3 + 4 + 5 = 15=> 18 - 15 = 3 so 3 is the duplicate

Trong ví dụ này, chúng ta có thể tìm nghiệm trong thời gian O[n] và không gian O[1]. Tuy nhiên, nó chỉ hoạt động trong trường hợp chúng tôi có một bản sao

Một phản ví dụ

Input: [1, 2, 3, 2, 3, 4]
Sum = 15As in this example we have n = 5,
Sum of 1 to 5 = 1 + 2 + 3 + 4 + 5 = 15/!\ Not working

Hướng này chẳng đi đến đâu. Nhưng đôi khi chúng ta cần thử công cụ để tìm ra giải pháp tối ưu nhất

Đánh dấu

Có một cái gì đó thú vị để đề cập đến. Cho đến nay, các giải pháp của chúng tôi không thực sự tận dụng thực tế là mỗi số nguyên nằm trong khoảng từ 1 đến n. Do ràng buộc thú vị này, mỗi giá trị có chỉ số tương ứng riêng trong mảng

Giải pháp là coi mảng cụ thể này là một loại danh sách được liên kết. Bất kỳ chỉ mục nào đang trỏ đến giá trị của chỉ mục đó

Chúng tôi lặp lại từng phần tử và đánh dấu chỉ mục tương ứng của nó bằng cách đặt dấu của nó thành dấu trừ. Nếu chúng tôi đã đánh dấu nó là phủ định, điều đó có nghĩa là chỉ mục của nó trùng lặp

Hãy xem một ví dụ cụ thể từng bước

Input: [2, 3, 3, 1]* Index 0:
    Absolute value = 2
    Put a minus sign to a[2] => [2, 3, -3, 1]* Index 1:
    Absolute value = 3
    Put a minus sign to a[3] => [2, 3, -3, -1]* Index 2:
    Absolute value = 3
    As a[3] is already negative, it means 3 is a duplicate

Trong Java

Giải pháp này là O[n] thời gian và O[1] không gian. Tuy nhiên, nó yêu cầu phải thay đổi danh sách đầu vào

kỹ thuật chạy

Có một giải pháp khác cũng coi mảng đã cho là một loại danh sách được liên kết [một lần nữa, điều này có thể thực hiện được do ràng buộc rằng mỗi số nguyên nằm trong khoảng từ 1 đến n]

Hãy cùng phân tích ví dụ

for i = 0; i < size[a]; i++ {
  for j = i+1; j < size[a]; j++ {
    if[a[i] == a[j]] return a[i]
  }
}

Với biểu diễn này, chúng ta có thể nói một cách đơn giản rằng một bản sao tồn tại khi một chu kỳ tồn tại. Hơn nữa, bản sao là điểm vào của chu trình [trong trường hợp này là phần tử thứ hai]

Nếu lấy cảm hứng từ thuật toán tìm chu trình của Floyd, chúng ta có thể rút ra thuật toán sau

• Bắt đầu hai con trỏ

  for i = 0; i < size[a]; i++ {
    for j = i+1; j < size[a]; j++ {
      if[a[i] == a[j]] return a[i]
    }
  }

  2 và

  for i = 0; i < size[a]; i++ {
    for j = i+1; j < size[a]; j++ {
      if[a[i] == a[j]] return a[i]
    }
  }

  3
• Đối với mỗi bước, chậm là di chuyển từng bước một với

  for i = 0; i < size[a]; i++ {
    for j = i+1; j < size[a]; j++ {
      if[a[i] == a[j]] return a[i]
    }
  }

  4, trong khi nhanh là di chuyển hai bước cùng lúc với

  for i = 0; i < size[a]; i++ {
    for j = i+1; j < size[a]; j++ {
      if[a[i] == a[j]] return a[i]
    }
  }

  5
• Khi

  for i = 0; i < size[a]; i++ {
    for j = i+1; j < size[a]; j++ {
      if[a[i] == a[j]] return a[i]
    }
  }

  6, chúng ta đang ở trong một chu kỳ

Thuật toán đã hoàn thành chưa? . Điểm vào của chu trình này sẽ trùng lặp. Chúng ta phải đặt lại

for i = 0; i < size[a]; i++ {
  for j = i+1; j < size[a]; j++ {
    if[a[i] == a[j]] return a[i]
  }
}