Cần giúp đỡ về hoán vị mảng con trong một Mảng

[thaidz199x (LemonTree)]

trên đây là minh họa về input output của bài toán và gợi ý code, Mong bác nào thông não cho em đoạn hàm Exchange cụ thể chi tiết với . Em cảm ơn

[rogp10]

Mình nhìn vào còn hoang mang mà cái này gọi là Rotate (xoay)

Bài này có hai cách dễ làm là ba bước đảo mảng và nhảy cóc (khó hơn ) đều O(n) chứ ở trên là cách thứ ba.

[thaidz199x (LemonTree)]

cảm ơn bác, em đi học thì slide thầy giáo có gợi ý như vậy nhưng đọc xong vẫn chưa làm được . Bác có bài viết nào liên quan thì reply em với ạ

[thaidz199x (LemonTree)]

Cảm ơn về keyword của bác nhé, em tìm ra tài liệu để tham khảo rồi ạ, rất cảm ơn <3

[bathudaide]

Cách hơi chuối

• Tạo hàm move() để “chuyển phần tử đầu tiên về cuối mảng”

• Để chuyển k phần tử đầu tiên về cuối mảng thì gọi k lần hàm move() là được

Để “chuyển phần tử đầu tiên về cuối mảng”

• Lưu lại phần tử đầu tiên

• Dời từng phần tử hiện tại lên vị trí trước nó arr[i] <= arr[i+1]

• Gán phần từ cuối cùng = phần tử đầu tiên (được lưu ở trên).

Bỏ C++ lâu quá rồi nên bạn xem code java đỡ nhé

static void rotate(int arr[], int k) {
	// Chuyển k lần
	for (int i = 1; i <= k; i++) {
		move(arr);
	}
}

static void move(int arr[]) {
	int i, n, tmp;
	n = arr.length; // kích thước mảng
	tmp = arr[0];
	for (i = 0; i < n - 1; i++) {
		arr[i] = arr[i + 1];
	}
	arr[i] = tmp;
}

public static void main(String[] args) {
	int arr[] = { 1, 2, 3, 4, 5 };
	int k = 3; // chuyển k phần tử
	// [1, 2, 3, 4, 5]
	rotate(arr, k);
	// [4, 5, 1, 2, 3]
}

[rogp10]

Cái này là O(kn) nhưng cách 2 cũng bắt đầu từ việc xoay đi 1 bước.

[Killua]

Bài này có 1 cách nữa O(n) nhưng bị tốn space thêm n nữa, trước mình làm do nó yêu cầu phải O(n) mới pass :’(

[rogp10]

Cách đó thì không tính tiền rồi

Giờ mình mới biết có cách block swap.

[thaidz199x (LemonTree)]

cảm ơn các bác đã góp ý ạ.