[LeetCode] Find the Distinct Difference Array

아르당·2026년 10월 23일

LeetCode

목록 보기
563/602
post-thumbnail

문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

인덱스가 0부터 시작하고 길이가 n인 배열 nums가 주어진다
배열 nums의 고유 차이 배열은 길이가 n인 배열 diff를 의미하고, diff[i]는 접두사 nums[0, ..., i]에 포함된 고유 요소의 개수에서 접미사 nums[i + 1, ..., n - 1]에 포함된 고유 요소의 개수를 뺀 값과 같다.
nums의 고유 차이 배열을 반환해라.

Example

#1
Input: nums = [1, 2, 3, 4, 5]
Output: [-3, -1, 1, 3, 5]

#2
Input: nums = [3, 2, 3, 4, 2]
Output: [-2, -1, 0, 2, 3]

Constraints

  • 1 <= n == nums.length <= 50
  • 1 <= nums[i] <= 50

Solved

class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        int[] diff = new int[n];
        boolean[] seen = new boolean[51];
        int distinct = 0;

        for(int i = 0; i < n; i++){
            if(!seen[nums[i]]){
                seen[nums[i]] = true;
                distinct++;
            }

            prefix[i] = distinct;
        }

        seen = new boolean[51];
        distinct = 0;

        for(int i = n - 1; 0 <= i; i--){
            suffix[i] = distinct;

            if(!seen[nums[i]]){
                seen[nums[i]] = true;
                distinct++;
            }
        }

        for(int i = 0; i < n; i++){
            diff[i] = prefix[i] - suffix[i];
        }

        return diff;
    }
}
profile
내 마음대로 코드 작성하는 세상

0개의 댓글