Giả sử chúng ta được cung cấp một mảng và được yêu cầu thực hiện sắp xếp chèn trên đó. Trong sắp xếp chèn, mỗi phần tử trong một mảng được chuyển đến vị trí chính xác của nó trong mảng. Chúng ta phải tìm ra tổng số ca cần thiết để sắp xếp một mảng. Tổng số lần dịch chuyển là một số nguyên và nếu mảng đã được sắp xếp, chúng tôi trả về 0.
Vì vậy, nếu đầu vào giống như input_array =[4, 5, 3, 1, 2], thì đầu ra sẽ là 8
[4, 5, 3, 1, 2] = 0 shifts [4, 5, 3, 1, 2] = 0 shifts [3, 4, 5, 1, 2] = 2 shifts [1, 3, 4, 5, 2] = 3 shifts [1, 2, 3, 4, 5] = 3 shifts
tổng số ca là =0 + 0 + 2 + 3 + 3 =8.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- length:=kích thước của input_arr
- temp_arr:=một danh sách mới có kích thước 1000001 được khởi tạo bằng các chữ số 0
- ans:=0
- đối với mỗi mục trong input_arr, hãy thực hiện
- val:=item
- while val> 0, do
- ans:=ans + temp_arr [val]
- val:=val - (val AND -val)
- val:=item
- while val <=1000000, do
- temp_arr [val]:=temp_arr [val] + 1
- val:=val + (val AND -val)
- ans:=length * (giá trị sàn của (length - 1) / 2) - ans
- trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(input_arr): length = len(input_arr) temp_arr = [0] * 1000001 ans = 0 for item in input_arr: val = item while val > 0: ans += temp_arr[val] val -= val & -val val = item while val <= 1000000: temp_arr[val] = temp_arr[val] + 1 val += val & -val ans = length * (length - 1) // 2 - ans return ans print(solve([4, 5, 3, 1, 2]))
Đầu vào
[4, 5, 3, 1, 2]
Đầu ra
8