【Codility Lesson2】Odd Occurrences In Array

Codility의 추천 ~JavaScript로 해결하는 알고리즘~ 의 실천편입니다.

문제



A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:

function solution(A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values ​​in A occur an even number of times.

어휘 메모


  • be paired with ~와 쌍이 되어
  • unpaired 쌍이 되지 않음
  • indexes 색인※ index 은 「인덱스」의 의미일 때의 복수형은 indexes , 「지표」의 의미일 때는 indices 입니다

  • 해법



    필요 지식


  • 애로우 함수
  • 고층 함수
  • Map 객체
  • map()
  • find()
  • Object.keys()
  • + 연산자
  • reduce()

  • 굵은 글씨로 하는 것은 첫견이었습니다.
    특히 reduce()는 처음에는 어려웠습니다.
    function solution(A) {
      const makeIntegerOcurrencesMap = (map, nextInteger) => {
        const isMissingKey = (key) => map[key] === undefined;
    
        if (isMissingKey(nextInteger)) {
          map[nextInteger] = 0;
        }
    
        ++map[nextInteger];
    
        return map;
      };
      const isOdd = (number) => number % 2 !== 0;
      const integerOccurrencesMap = A.reduce(makeIntegerOcurrencesMap, {});
    
      return +Object.keys(integerOccurrencesMap).find((integer) =>
        isOdd(integerOccurrencesMap[integer])
      );
    }
    
    
    

    참고



    알고리즘 도감 그림에서 보는 26개의 알고리즘 세계에서 가장 강력한 9 알고리즘 어쨌든! 알고리즘 최초의 JavaScript 제3판 ―ES2015 이후의 최신 웹 개발 철저 예해 로얄 영문법 개정 신판 <

    철저한 예해 로얄 영문법 개정 신판

    좋은 웹페이지 즐겨찾기