Portfolio

문제

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:


Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].

Example 2:


Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.

Example 3:


Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.

Constraints:

1 <= changed.length <= 105

0 <= changed[i] <= 105

풀이

은찬


const findOriginalArray = (changed) => {
    const length = changed.length;
    const half = Math.floor(length / 2);
    const number = Array(100001).fill(0);
    const answer = [];
    
    changed.sort((a, b) => a - b);
    
    for(let i = 0; i < length; i++){
        number[changed[i]]++;
    }
    
    for(let i = 0; i < length; i++){
        if(number[changed[i]] && number[changed[i] * 2]){
            number[changed[i]]--;
            
            if(changed[i]){
                number[changed[i] * 2]--;
                answer.push(changed[i]);
            } else{
                if(number[0]){
                    number[0]--;
                    answer.push(0);
                }
            }
        }
    }
    
    return answer.length * 2 === length ? answer : [];
};

효성

풀긴 했는데 엄청 느리네요..ㄸ


var findOriginalArray = function(changed) {
    
    if(changed.length % 2 !== 0) return []; 
    changed.sort((a, b) => b - a);
    
    const answer = [];
    
    while(changed.length) {
        let isBreak = false;
        const original = changed.pop();
        const doubled = original * 2;
        for(let i=changed.length-1; i>=0; i--) {
            if(changed[i] === doubled) {
                answer.push(original);
                changed.splice(i, 1);
                isBreak = true;
                break;
            }
        }
        if(!isBreak) return [];
    } 
    return answer;
};

돌아온 코테 용사 재영 (슬럼프 극복하구 왔어요~~)


/**
 * @param {number[]} changed
 * @return {number[]}
 */
var findOriginalArray = function (changed) {
  const changedLength = changed.length;
  if (changedLength % 2) return [];

  const answer = [];
  const obj = {};

  for (let i = 0; i < changed.length; i += 1) {
    const now = changed[i];
    obj[now] = (obj[now] ?? 0) + 1;
  }

  for (let key in obj) {
    if (obj[key] === 0) continue;
    if (!obj[key * 2]) return [];
    if (key === "0") {
      if (obj[key] % 2) return [];
      for (let i = 0; i < obj[key] / 2; i += 1) {
        answer.push(0);
      }
      continue;
    }

    const cnt = obj[key];
    for (let i = 0; i < cnt; i += 1) {
      answer.push(key);
    }

    obj[key] = 0;
    obj[key * 2] -= cnt;
  }

  return answer;
};

252ms, faster than 98% / memory lower than 85% 63.2MB

Find Original Array From Doubled Array

문제

풀이

풀긴 했는데 엄청 느리네요..ㄸ