Block swap algorithm for array rotation

algorithm
java

(mmmm) #1

Mọi người cho em hỏi bài dưới nếu mảng 7 phần tử, n =2, d=10 thì sau khi swap 7 phần tử xong phải làm gì ạ? vì đề ko hề bắt là d < size mảng.

Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.

Rotation of the above array by 2 will make array


(Nguyễn Đình Anh) #2

Bạn có thể để ý: d = 7 thì sau khi xoay ta sẽ được một mảng y hệt như cũ, vậy nên chỉ cần xoay d' = d % 7 là được :slight_smile:


Tiện mình cũng đưa ra giải thuật bày này luôn :slight_smile: Nếu bạn để ý chút thì sẽ thấy :slight_smile:

  • Các phần tử cần xoay sẽ di chuyển về vị trí = size - d + vị trí của số đó trong mảng
  • Còn vị trí của các phần tử còn lại sẽ thành A[d + vị trí của số đó trong mảng]

Nếu bạn vẫn chưa hiểu thì có thể xem qua code của mình ở đây nhé :slight_smile:


Giải bài 189 Rotate Array O(N)
(mmmm) #3

ủa bạn ơi, bên kia size là length của mảng hay size là số phần dịch chuyển vậy? sao bạn lại để
int[] output = new int[size];


(Nguyễn Đình Anh) #4

size là length của mảng bạn nhé :slight_smile:


(mmmm) #5

hình như đề size chỗ đó là số phần tử dịch chuyển mà


(Nguyễn Đình Anh) #6

Trong thuật toán của mình thì size là length của mảng, bạn có thể đổi lại để giống đề. Mình chỉ đưa ra ý tưởng thôi :slight_smile:


(mmmm) #7

Cảm ơn bạn nhiều nha, thuật toán bạn hay quá, mình chẳng nghĩ ra được :smile:


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?