-
[leetcode] Squares of a Sorted Array알고리즘 2021. 9. 3. 22:49
https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3574/
Explore - LeetCode
LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore.
leetcode.com
Success
오름차순으로 정렬된 배열이 주어졌을 때 , 각 원소의 값을 제곱한 후 오름차순 되어 있는 상태로 반환 해야한다.
풀이
각 원소에 값을 제곱을 하여 새로 값을 할당 시킨 후 정렬시킨다.
class Solution { public int[] sortedSquares(int[] nums) { for (int i=0; i<nums.length; i++) { nums[i] = nums[i]*nums[i]; } Arrays.sort(nums); return nums; } }
다른방법으로는 새로운 배열을 만든후 투포인터를 이용하는 한다.
반복문을 뒤에서 부터 돌게하여 왼쪽 끝에 있는 인덱스의 값과 오른쪽 끝에 있는 인덱스의 값을 비교하여 큰 값을 제곱한 후 새로운 배열에 맨 뒤부터 채워가는 방법이다.
이 방법을 사용하면, 배열은 새로 하나 만들어야 하지만 정렬하는 과정은 필요없게 된다.
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] Find Numbers with Even Number of Digits (0) 2021.11.06 [leetcode] 485. Max Consecutive Ones (0) 2021.11.06 [leetcode] Find All Numbers Disappeared in an Array (0) 2021.09.03 [leetcode] Third Maximum Number (0) 2021.09.03 [leetcode] Max Consecutive Ones II (0) 2021.09.03