Tìm nếu một mảng là một chuỗi trong thời gian O (n) và O (1)

Question

Cho một mảng có thể chứa các bản sao, Làm thế nào chúng ta có thể tìm thấy nếu nó là một chuỗi?

Ví dụ: {7, 3, 5, 4, 6, 2}

là một chuỗi 2, 3, 4, 5, 6, 7

Sắp xếp là một giải pháp rõ ràng. Làm thế nào chúng ta có thể làm điều này trong thời gian O (n) và O (1)?

Answer 1

Hãy thử của tôi:

1. Xác định min và max – O (n)
2. Hãy một mảng các giá trị nullable kích thước của mảng ban đầu – O (n) (Vâng, thiếu yêu cầu không gian ở đây)
3. Lặp lại mảng ban đầu (O (n)) và đặt số bạn tìm thấy ở chỉ mục (số - phút), nếu bạn tìm thấy giá trị ở đó, bạn không có chuỗi, nếu bạn đến kết thúc và không có vị trí nào được xác nhận quyền sở hữu, bạn có một chuỗi

public bool IsSequence(int[] values) 
{ 
    var min = values[0]; 
    var max = values[0]; 
    foreach (var value in values) 
    { 
     min = min > value ? value : min; 
     max = max > value ? max : value; 
    } 

    if ((max - min + 1) != values.Length) 
     return false; 

    var testingArray = new int?[values.Length]; 
    foreach (var value in values) 
    { 
     var index = value - min; 
     if (testingArray[index].HasValue) 
      return false; 
     else 
      testingArray[index] = value; 
    } 
    return true; 
} 

Answer 2

giả 1,2,3,3,4,1 là một chuỗi không được phân loại hợp lệ và 2,4,6,8 là một chuỗi giá trị (của bước hai) là tốt, nhưng không phải là 1,3,5,9 (7 là mất tích) và giả sử mảng đầu vào có thể được ghi đè,

1. xác định tối đa và tối thiểu: thời gian O (n), O (1). Bạn có thể sử dụng vị trí đầu tiên và cuối cùng của mảng cho việc này.
2. xác định bước. Bước này là hệ số ít phổ biến nhất của tất cả a_n - min
3. nếu chúng quá xa nhau (max - min > (count + 1) * step), đây không thể là chuỗi. Nếu không,
4. thực hiện sắp xếp số nguyên tại chỗ. Cho đến khi bắt đầu> kết thúc:
   • xem xét vị trí đầu tiên. Hãy để cho giá trị có thể v_0
   • phép vị trí mục tiêu của mình khi chúng ta giả định không có bản sao ((v_0 - min)/step + start) được i
     • nếu vị trí mục tiêu nhỏ hơn start, đó là một trùng lặp. Di chuyển nó về phía sau và giảm con trỏ cuối
     • nếu vị trí mục tiêu lớn hơn end, một số phần tử bị thiếu trong chuỗi. Yêu cầu mảng không phải là một chuỗi.
   • nếu nguyên tố này là ở vị trí mục tiêu, tăng con trỏ bắt đầu và các min tham khảo
   • khác nếu các phần tử ở vị trí đích là ít hơn mức tối thiểu tham chiếu hoặc bằng v_0, trao đổi nó đến cùng của mảng và giảm con trỏ kết thúc. Đó là một bản sao.
   • khác trao đổi phần tử ở vị trí đích với v_0.
5. yêu cầu bồi thường mảng một chuỗi

Các nguyên tại chỗ loại là O (n).Trong mỗi bước nó hoặc là:

• rút ngắn mảng đầu vào và giữ tất cả các yếu tố được sắp xếp tại các vị trí mục tiêu của họ hoặc
• loại một hoặc hai yếu tố trước đó không được phân loại vào vị trí mục tiêu của họ.

Khi kết thúc sắp xếp, mỗi phần tử là bản sao trong khối trùng lặp hoặc ở vị trí chính xác của nó trong khối được sắp xếp.

Lưu ý rằng bướC# 3 có thể bị bỏ qua. # 4 sẽ xác định chính xác đây không phải là một chuỗi, mặc dù chậm hơn.

Nếu bước phải là 1, sau đó thuật toán này có thể được đơn giản hóa một chút (xem phiên bản # 1)

Answer 3

thuật toán này (Python) phá hủy các mảng ban đầu, nhưng nếu không đáp ứng O (n) thời gian và O (1) thêm không gian.

# INPUT: An array 'arr' of N integers. 
# OUTPUT: If the array consists exactly of the integers 
#   S, S+1, ..., S+N-1, for some S, in any order, 
#   then modifies 'arr' into a sorted array and returns it. 
#   Otherwise, returns False, and 'arr' may have been modified. 
def sort_sequence (arr): 
    the_min = min(arr) 
    the_max = max(arr) 
    if the_max - the_min != len(arr) - 1: 
     return False 
    for i in range(len(arr)): 
     arr[i] -= the_min 
    for i in range(len(arr)): 
     while arr[i] != i: 
      j = arr[i] 
      t = arr[j] 
      if t == j: 
       return False 
      arr[j] = j 
      arr[i] = t 
    for i in range(len(arr)): 
     arr[i] += the_min 
    return arr 

Tôi chưa chính thức chứng minh rằng nó vẫn hoạt động.

Tại sao O (n) này? Trong vòng lặp cuối cùng, sau khi một phần tử được đưa vào vị trí chính xác của nó, nó chỉ có thể được truy cập một lần nữa - hoặc ở đầu một vòng lặp bên trong khác, nơi nó được nhìn thấy ở đúng vị trí, hoặc nơi nó được tìm thấy theo cách của phần tử trùng lặp (phần if t == h).