Crushing Job Interviews(DSA) - 정렬된 제곱 배열

질문

난이도: 매체의 종류

오름차순으로 정렬된 비어 있지 않은 정수 배열을 가져와 원래 정수의 제곱도 오름차순으로 정렬된 동일한 길이의 새 배열을 반환하는 함수를 작성하세요.

샘플 입력

array = [1, 2, 3, 5, 6, 8, 9]

샘플 출력

[1, 4, 9, 25, 36, 64, 81]

최적의 공간 및 시간 복잡성:

O(n) 시간 | O(n) 공간 - 여기서 n은 입력 배열의 길이입니다.

생각

면접관에게 주어진 원래 배열을 변경할 수 있는지 또는 중복 배열을 만들어야 하는지 물어보는 것이 중요합니다.

따라서 이를 해결하는 두 가지 방법이 있습니다. 첫 번째는 다음과 같습니다.

배열을 반복합니다

.

각 수를 제곱하고

새 어레이에 추가

어레이 정렬

이 솔루션은 간단하지만 더 잘할 수 있습니다.

두 번째 솔루션에서는 포인터를 사용합니다.

P.S: Pointers in arrays context are used to keep track of the position while iterating through it.

따라서 우리가 할 일은 다음과 같습니다.

배열을 반복합니다.

포인터를 사용하여 배열의 첫 번째 위치와 마지막 위치를 추적합니다.

포인터가 가리키는 항목의 절대값을 비교합니다.

첫 번째 인덱스 값이 더 크면 우리가 만든 중복 배열에서 반복하는 인덱스에 해당 값을 배치하고 첫 번째 포인터를 1씩 증가시킵니다.

ELSE, 반복 중인 현재 인덱스에 다른 포인터 배열 값을 배치하고 두 번째 포인터를 1씩 줄입니다.

혼란스럽나요? 그렇긴 한데 코드를 한 번 보면 이해가 더 잘 되실 거라 확신합니다. 첫 번째 솔루션은 매우 간단하고 솔루션을 쉽게 생각해 낼 수 있다고 믿기 때문에 기록하지 않을 것입니다. 그래도 원하신다면 댓글 달아주시면 올려드리겠습니다.

솔루션(2차)

function sortedSquaredArray(array) {
  const toReturn = [...array]
  let smallerValueIdx= 0
  let largerValueIdx = (array.length) - 1
  for (let idx = array.length - 1; idx >=0; idx--) {
    const smallerVal = array[smallerValueIdx]
    const largeVal = array[largerValueIdx]

    if (Math.abs(smallerVal) > Math.abs(largeVal)) {
      toReturn[idx] =smallerVal * smallerVal
      smallerValueIdx++
    }
    else{
      toReturn[idx] = largeVal * largeVal
      largerValueIdx --
    }
  }
  return toReturn;
}

의심의 여지가 있습니까? 더 나은 솔루션이 있습니까? 아래에 의견을 남기고 토론을 시작합시다.

코딩에 대한 더 멋진 콘텐츠를 보려면 인스타그램에서 나를 팔로우하세요.