879210. Distinct Sorted
Basic
Distinct Sorted
Slug: distinct-sorted--124713
Difficulty: Basic
Id: 879210
Topic Tags: Java, STL, Java-Collections
Company Tags: None
Summary
This problem is about finding all the unique elements in a sorted array. Given an integer array nums and an integer n, find all distinct elements in the range [0, n]. The output should be sorted in ascending order.
Detailed Explanation
To solve this problem, we can iterate through the given array and keep track of the unique elements. We will use a set to store these unique elements. Then, we can sort the set and return it as our result.
Here is a step-by-step breakdown of the solution:
- Initialize an empty set
uniqueElementsto store the unique elements. - Iterate through the given array
nums. - For each element in the array, check if it is within the range
[0, n]. If it is, add it to the setuniqueElements. - Sort the set
uniqueElementsand return it as our result.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing unique elements in a set.
Optimized Solutions
Java
import java.util.*;
public class DistinctSorted {
public static List<Integer> findDistinct(int[] nums, int n) {
Set<Integer> uniqueElements = new HashSet<>();
for (int num : nums) {
if (num >= 0 && num <= n) {
uniqueElements.add(num);
}
}
List<Integer> result = new ArrayList<>(uniqueElements);
Collections.sort(result);
return result;
}
}