다음과 같이 정확히 3개의 요소 -1, 0 및 1의 빈도를 포함하는 숫자 배열이 있다고 가정합니다. -
const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1];
그러한 배열을 취하는 JavaScript 함수를 작성해야 합니다. 함수는 값을 저장하기 위해 추가 배열을 사용하지 않고 이 특수 배열을 제자리에 정렬하기만 하면 됩니다.
유일한 조건은 함수가 선형 시간 함수여야 한다는 것입니다(하나의 반복만 사용).
예시
다음은 코드입니다 -
const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1]; const sortSpecialArray = (arr = []) => { const swap = (a, b) => { let middle = arr[a] arr[a] = arr[b] arr[b] = middle }; let left = 0; let middle = 0; let right = arr.length-1; while(middle <= right){ if(arr[middle] === -1){ swap(left++, middle++); }else if(arr[middle] === 0){ middle++; }else if(arr[middle] === 1){ swap(right--, middle); } }; }; sortSpecialArray(arr); console.log(arr);
출력
다음은 콘솔 출력입니다 -
[ -1, -1, 0, 0, 0, 0, 1, 1, 1, 1, 1 ]