Hỏi giải thuật bài xoay phần tử trong mảng

[IT_Hoai_Tam (It Hoài Tâm)]

Giả sử ta có 1 array: [1,2,3,4,5,6,7]
Viết function để “xoay” phần tử trong mạng, d là số lần xoay

d = 1 => [2,3,4,5,6,7,1]
d = 2 => [2,3,4,5,6,7,1] => [3,4,5,6,7,1,2]
d = 3 => [2,3,4,5,6,7,1] => [3,4,5,6,7,1,2] => [4,5,6,7,1,2,3]

[anon12276517]

Chạy vòng for từ 1 đến d, mỗi lần lặp thì đảo phần từ đầu xuống cuối là được mà

[qloved (Quân)]

Chạy vòng for từ 1 đến d, mỗi lần lặp thì đảo phần từ đầu xuống cuối là được mà

Bổ sung cho bạn
n là số phần tử trong mảng ban đầu

1. Dễ thấy là xoay khi xoay d lần thì mảng kết quả sẽ là 1 mảng có n phần tử với c=n-d phần tử đầu tiên là c phần tử cuối của mảng ban đầu và d phần tử cuối của mảng kết quả là d phần tử đầu tiên của mảng ban đầu với d<n.
2. Nếu d >= n thì cũng chỉ xoay d’ lần với d’ là phép chia lấy dư của d cho n mà thôi

[rogp10]

Có thể quay với O(1) mem (ừ) và O(n) time. 1 for.

[trungnguyenuit (Trung Nguyen)]

bạn for từ 0 tới d, mỗi lần lặp như vậy thì append cái a[0] vào cuối array, và xoá a[0] đi.
như vậy ko cần phải để ý xem len của array là bao nhiêu, và d là bao nhiêu.

[kienonline19 (Nguyen Kien)]

Cách giải của mình như sau:

import java.util.Arrays;

public class ArrayRotation {
	
	public static void main(String[] args) {
		
		/*
			* Input: [1, 2, 3, 4, 5, 6] and d = 3
			* Output: [2, 3, 4, 5, 6, 1] --> [3, 4, 5, 6, 1, 2] --> [4, 5, 6, 1, 2, 3]
			* Test: array: null, [], [1,n]
		*/

		// Test: [1,n]
		int[] arr = {1, 2, 3, 4, 5, 6, 7};
		StringBuilder str = new StringBuilder();
		for (int number: arr) {
			str.append(Integer.toString(number));
		}

		int d = 3;
		for (int i = 0; i < d; ++i) {
			char temp = str.charAt(0);
			str.deleteCharAt(0);
			str.append(temp);
		}

		char[] arrStr = str.toString().toCharArray();
		for (int i = 0; i < arr.length; ++i) {
			
			arr[i] = arrStr[i] - '0';
		}

		System.out.println(Arrays.toString(arr));
	}
}

[noz1995 (Trần Hoàn)]

void XoayMang(int Input[], int n, int d)
{
    int* Temp = new int[n];
    for (int i = 0; i < n; i += 1)
        Temp[i] = Input[(i + d) % n];
    for (int i = 0; i < n; i += 1)
        Input[i] = Temp[i];
    delete[] Temp;
}

[kienonline19 (Nguyen Kien)]

Em chưa hiểu 2 chỗ:

1. sao anh lại nghĩ ra index: (i + d) % n ?
2. tại sao không sử dụng ++i thay vì i += 1 ?

[noz1995 (Trần Hoàn)]

1.1. Khi di chuyển 1 lần, a[0] giờ nằm ở a[1]
1.2. Khi di chuyển 4 lần, a[0] nằm ở a[4]
1.3. Khi di chuyển n lần, a[0] đứng yên
1.4. Khi di chuyển n + 1 lần, a[0] nằm ở a[1]
⇨ Khi di chuyển d lần, a[0] nằm ở a[d % n]
1.5. Thứ tự của mảng là không đổi ⇨ Khi di chuyển d lần, mỗi phần tử a[i] đều đi đến vị trí a[i + d % n]
1.6. Nếu i + d % n > n thì lại phải % n 1 lần nữa
1.7. (i + d % n) % n = (i + d) % n

2. Vì mình thích thế.

[anon12276517]

Cách của bạn sẽ bị lỗi khi mà chữ số trong List có từ 2 chữ số trở lên. Mình thấy cách này tối ưu hơn.

import java.util.Arrays;


public class Spin_Array 
{
    public static void main(String[] args) 
    {
        // Var
        int[] arr = {1,2,3,4,5,6,7};  
        
        // Test
        System.out.println(Arrays.toString(spin(arr, arr.length, 1)));
        
    }
    
    private static int[] spin(int[] arr, int size, int d)    
    {
        if(d >= size)
        {
            d = d % size;
        }
        
        int[] output = new int[size];
        
        for(int i = 0; i < d; i++)
        {
            output[size - d + i] = arr[i];
        }
        
        for(int i = 0; i < size - d; i ++)
        {
            output[i] = arr[d + i];
        }
        
        return output;
    }
}