배열 [1, 2, 3, a, b, c]이 주어지면 다른 모든 요소의 위치가 바뀌도록 배열을 재정렬하는 방법을 작성하십시오. 출력은 [1, a, 2, b, 3, c]이어야합니다.배열 요소의 순서를 바꿉니다
1. 공간을 사용하여 더 빨리 작동하는 algorithm을 작성하십시오. 2. 허용되는 경우 extra-space, time-complexity에 얼마나 많은 개선이 이루어질 수 있습니다.
이것은 인터뷰 질문입니다. 여러 가지 설명이 나와있는 SO, Interview test - rearrange the array, Reordering of array elements, Array movement from a1,..,an,b1,..,bn to a1,b1,..,an,bn 및 elsewhere의 게시물이 있지만 그 내용이 명확하고 구체적이지 않습니다. 위의 첫 번째 질문에 대한 해결책은 O(n^2)입니다. 그러나 그것을 개선 할 가능성이있는 것처럼 보입니다. 그러나 나는이 글들로부터의 설명, 특히 이론적 논문을 언급하는 일부를 정말로 언 급하지 않습니다. 첫 번째 질문에 대한 시간 복잡성 (O(n^2) 이상)을 향상시키기위한 단순한 의사 코드가 큰 경우에 유용합니다.
둘째로, 하나의 스토리지 배열을 사용하여 시간 복잡도를 O(n)으로 줄일 수 있습니다. 하지만 더 개선 할 방법이 없습니다. 그것이 가능하다면, 나는 그것을 듣는 것을 좋아할 것입니다.
내 첫 번째 시도에 대한 코드 (auxillary 스토리지를 사용하지 않고)는 여기에 있습니다 :
import java.util.Arrays;
public class SwapHalfArrayElements {
public static void main(String[] args){
Object[] arr = {1,2,3,'a','b','c'};
System.out.println("before sorting "+Arrays.toString(arr));
rearrageArray(arr);
System.out.println("After sorting "+ Arrays.toString(arr));
}
private static void swap(Object[] arr, int index1, int index2){
Object temp=arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
}
private static void rearrageArray(Object[] arr){
int n=arr.length/2;
for (int i=1;i<n;i++){
for (int j=-i;j<i;j+=2){
swap(arr,n+j,n+j+1);
}
}
}
}
첫 번째 배열을 출력 pls로 변환하는 방법에 대해 좀 더 자세히 설명해 주시겠습니까? 그것을 알아낼 수 없습니다. – Warlord
@Warlord : 나는 배열의 중간에서 교환 시작하고 바깥쪽으로 이동 –