-
[leetcode] 977. Squares of a Sorted Array알고리즘 2021. 11. 6. 15:51
[Success]
내림차순으로 정렬된 정수 배열이 주어졌을 때, 내림차순으로 정렬된 각 인덱스 값의 제곱 구하는 문제
[풀이]
각 인덱스의 값의 제곱을 구한 후 해당 인덱스에 다시 할당시킨다.
제곱의 값으로 다 채워진 후에는 해당 배열을 내림차순으로 정렬.
class Solution { public int[] sortedSquares(int[] nums) { for (int i=0; i<nums.length; i++) { int square = nums[i] * nums[i]; nums[i] = square; } Arrays.sort(nums); return nums; } }
[leetcode solution]
[-10, -5, 1, 2, 4, 7] 배열이 주어졌을때 해당 값들을 제곱하여 재할당하면 [100, 25, 1, 4, 16, 49] 의 값으로 세팅된다.
이를 다시 내림차순으로 정렬하면 [1, 4, 16, 25, 49, 100]
이 때 제곱하여 재할당하는 시간복잡도는 O(n) , 내림차순으로 정렬하는 시간복잡도는 O(n log n) 의 비용이 들어간다.
위 방법이 아닌 Two-Point 방법으로 접근하면 시간복잡도를 O(n) 으로 해결 할 수 있다.
1. 제곱의 수를 새롭게 할당할 배열을 하나 선언한 후 nums 배열을 뒤에서 부터 접근한다.
2. 첫번째 값과 마지막 값에 각각의 left 와 right 라는 포인터를 두고 비교를 하는데 이 때 절대값으로 비교를 하고 left 와 right 중 어느 수를 제곱할지를 결정한 후에 포인터 이동을 시켜준다.
3. 제곱대상이 된 수를 제곱을 해준 후 새로운 배열에 뒤에서 부터 할당시켜주면 내림차순으로 완성 될 수 있다.
class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; int left = 0; int right = n - 1; for (int i = n - 1; i >= 0; i--) { int square; if (Math.abs(nums[left]) < Math.abs(nums[right])) { square = nums[right]; right--; } else { square = nums[left]; left++; } result[i] = square * square; } return result; } }
'알고리즘' 카테고리의 다른 글
[leetcode] 88. Merge Sorted Array (0) 2021.11.08 [leetcode] 1089. Duplicate Zeros (0) 2021.11.07 [leetcode] Find Numbers with Even Number of Digits (0) 2021.11.06 [leetcode] 485. Max Consecutive Ones (0) 2021.11.06 [leetcode] Squares of a Sorted Array (0) 2021.09.03