LeetCode[JS] > 1913. Maximum Product Difference Between Two Pairs

🧩문제링크

https://leetcode.com/problems/maximum-product-difference-between-two-pairs/

🔨문제풀이

이 문제는 처음에 sort로 정렬해서 1,2번째로 가장 큰수, 1,2번째로 가장 작은 수들을 바로 이용하는 방식으로 풀었는데 시작복잡도를 더 최적화 하는방법이 있었고 그 방법이 아래 방법이다. 단순히 nums의 모든 원소들을 sorting 하는방식은 시간복잡도나 O(nlogn)이고 아래 풀이의 시간복잡도는 O(n)이다.  ( 참고로 js에서 사용하는 sort 함수의 시간복잡도는 O(nlogn)이다. ) 

/**
 * second try
 * time complexity O(nlogn)
 * @param {number[]} nums
 * @return {number}
 */
var maxProductDifference = function (nums) {
    let arr = nums.slice(0, 4);

    arr.sort((a, b) => b - a);

    for (let i = 4; i < nums.length; ++i) {
        let n = nums[i];

        if (n < arr[3]) {
            arr[2] = arr[3]
            arr[3] = n;            
        } else if (n < arr[2]) {
            arr[2] = n;
        } else if (n > arr[0]) {
            arr[1] = arr[0];
            arr[0] = n;
        } else if (n > arr[1]) {
            arr[1] = n ;
        }
    }

    return arr[0] * arr[1] - arr[2] * arr[3];
};