[leetcode] (Array101) 977. Squares of a Sorted Array

 

Answers

mine : 리스트로 오름차순정렬까진 가능했지만 배열로 리턴하는 부분에서 막혔다. 해결법을 찾는 것보다 솔루션 보고 배우는 게 낫다 싶어서 이동.

=> 애초에 바꿔치기 될 대상이니 원래 배열의 값을 유지할 필요가 없다. 배열을 그대로 재활용하는 것이 방법.

class Solution {
    public int[] sortedSquares(int[] nums) {
        
        if (nums == null) {
            throw new IllegalArgumentException();
        }
        
        List<Integer> list = new ArrayList<>();
        
        for (int num : nums) {
            list.add(num * num);
        }

        return ;
        
    }
}

https://leetcode.com/problems/squares-of-a-sorted-array/solutions/4807685/beats-100-users-c-java-python-javascript-3-approaches-explained

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;
    }
}

* no need to declare new array object

 

기수정렬 응용

Approach 1( Radix Sort )

1. Squared and stored the values in same array.
2. Instead of using sort function, we are using radix sort to reduce complexity.

Complexity

• Time complexity:
  O(n)
• Space complexity:
  O(n)

class Solution {
    public int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    public void countSort(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10];

        for (int i = 0; i < arr.length; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }

    public void radixSort(int[] arr) {
        int max = getMax(arr);

        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(arr, exp);
        }
    }

    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        radixSort(nums);
        return nums;
    }
}

---

Things I Learned

nums.length()

Arrays.sort -> https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html

기수정렬 : 자릿수로 비교하여 정렬하는 방법. [222, 96, 5, 2]의 배열이 주어졌다면 1의 자리수를 기준으로 정렬을 시작한다. 이어서 10의 자리수로 정렬, 100의 자리수로 정렬한다. (링크 추가)