Với một mảng [A1B2C3D4] chuyển sang [abcd1234]

Question

ràng buộc:

1. O (1) không gian
2. O (n) Thời gian

Nó không phải là một câu hỏi bài tập về nhà chỉ một câu hỏi thú vị tôi đã gặp.

Dưới đây là một số giải pháp mà tôi có thể nghĩ ra nhưng không có gì thực hiện trong các ràng buộc nhất định.

Phương pháp 1

* Với O (n) bộ nhớ *

• Divide mảng trong hai phần đệ quy. (tiếp tục chia cho đến khi kích thước < = 2 cho mỗi vấn đề phụ)
• Sắp xếp từng vấn đề phụ với mảng đầu tiên và số ở cuối.
• Merge tiểu vấn đề mảng

Phương pháp 2

Trong O (n log n) thời gian

• Sắp xếp mảng thứ tự từ điển dựa nó trở nên 1234abcd
• Đảo ngược cả hai nửa của mảng 4321dcba
• Đảo ngược toàn bộ chuỗi abcd1234

Phương pháp 3

Nếu phạm vi các số đã được xác định

Ngoài ra nếu trường hợp là con số trong một phạm vi cụ thể sau đó tôi có thể khởi tạo một int nói track = 0; Và đặt bit thích hợp khi tôi bắt gặp một số trong mảng ví dụ: (1 < < a [2]). 1. Hoán đổi bảng chữ cái thành nửa đầu của mảng 2. Đánh dấu số trong biến theo dõi 3. sau đó sử dụng bản nhạc để điền vào nửa sau của mảng.

Phương pháp 4 Chúng tôi có thể sử dụng Phương pháp 3 với HashMap nếu chúng tôi muốn loại bỏ ràng buộc phạm vi số nguyên nhưng sau đó sẽ cần nhiều bộ nhớ hơn.

Không thể nghĩ ra cách tốt hơn để giải quyết vấn đề chung trong khoảng thời gian O (1) và O (n).

Vấn đề Generic đây đề cập đến:

Cho một x1y1x2y2x3y3 chuỗi .... xnyn nơi x1, x2 là bảng chữ cái x1 < x2 < .... < xn và y1y2 ... yn là các số nguyên.y1 y2 < < .... < yn Sắp xếp các đầu ra như x1x2 ... xny1y2 ... yn

Bất kỳ lời đề nghị?

Answer 1

n là gì? Giả sử rằng n là kích thước của đầu vào:

Điều này được gọi là sự chuyển đổi của danh sách. Về bản chất, bạn phải chuyển đổi danh sách các cặp (a,1),(b,2),(c,3),(d,4) thành một cặp danh sách (a,b,c,d),(1,2,3,4). Đó là hoạt động tương tự như transpose của một ma trận.

Dù sao, bạn phải nghĩ về cấu trúc như mảng k-chiều, trong đó k = lg n. Sự chập chững của mảng là những gì bạn nhận được khi bạn "di chuyển" giá trị tại chỉ mục i đến chỉ mục i bitwise xoay. Trong trường hợp này, chúng tôi muốn xoay các chỉ số ngay 1 bit. Điều này có nghĩa là chập là một hoán vị với độ dài chu kỳ cực đại của k. Bí quyết là sau đó chọn một chỉ mục từ mỗi chu kỳ - điều này sẽ luôn bao gồm 0 và n-1.

EDIT: Trên thực tế, những gì bạn có thể muốn là phân hủy hoán vị thành một sản phẩm chuyển vị. Sau đó, tất cả những gì bạn cần làm là hoán đổi.

Answer 2

Đây là thuật toán của tôi trong O (n).

trống cycle_leader (int * arr, int n) {

for (int i = 1; i < n/2; i+= 2) 
{ 
    int j = i; 
    int save; 
    int tmp = arr[i]; 

    do{ 
     if (j & 1) //odd index element 
      j = n/2 + j/2; 
     else 
      j = j/2; 

     save = arr[j]; 
     arr[j] = tmp; 
     tmp = save; 
    } while(j != i); 
} 

}

Answer 3

Giải pháp:

1. đầu tiên (chỉ số 0) và cuối cùng (chỉ số n-1) làm đừng di chuyển.
2. Tổng số di chuyển là (n - 2)

3. Phần tử số chẵn trong nguồn là bảng chữ cái. Họ di chuyển vào nửa đầu.

   target = j/2 // n là chẵn hay

4. yếu tố số Odd trong nguồn là những con số, và họ di chuyển vào hiệp hai.

   target = n/2 + sàn (j/2)

5. Bắt đầu từ yếu tố 1th, di chuyển đến vị trí mục tiêu của nó.

6. Di chuyển những gì bạn tìm thấy ở vị trí mục tiêu đến đích và như vậy cho đến khi vòng lặp được tạo. Lưu ý 1: Đôi khi, vòng lặp không bao gồm tất cả các phần tử trong danh sách, , tiếp tục với j + 2 Lưu ý 2: Đôi khi, ở cuối vòng lặp, giải pháp mong muốn sẽ đạt được, nhưng nếu chúng ta tiếp tục , mảng sẽ bị tranh giành lần nữa. Để khắc phục điều này, hãy đếm số chuyển động đã xảy ra và cắt khi nó đạt đến n - 2.

Bạn có thể thử chạy mã, tạo bản sao và chỉnh sửa ở đây Online Java Compiler IDE

---

int maxShifts = n - 2; // This is required to fix going around and messing up. 
int shifts = 0; 

for (int i = 1; i < n && shifts < maxShifts; i+=2) { 
    int source = i; 
    char itemToMove = array[source]; 
    do { 
    int target; 
    if (source % 2 == 0) { 
     target = source/2; // Even index is an alphabet 
    } else { 
     target = n/2 + source/2; // Odd index is a digit, that goes in the second half 
    } 
    char tmp = array[target]; 
    array[target] = itemToMove; 
    itemToMove = tmp; 

    shifts++; 
    source = target; 

    } while (i != source /*&& shifts < maxShifts*/); // Full cycle reached 

} 

Answer 4

Hoặc, bạn có thể sử dụng Python hùng mạnh, và dịch nó sang java:

a = [1,'a',2,'b',3,'c',4,'d'] 
a = a[0:len(a):2] + a[1:len(a):2] 
print(a) #this will print [1,2,3,4,'a','b','c','d']