배열의 중복 요소를 필터링하는 코드를 작성했습니다. 효율적인지, 너무 많은 객체가 생성 된 경우 배열과 목록을 모두 사용하는지 여부에 대한 귀하의 의견을 알고 싶습니다. 인터뷰 준비 중입니다. 저는 람다 (고유 한) 또는 도우미 메서드에 관심이 없습니다. Set, HashSet을 사용하지 않고도 내가 작성한 내용에서 무엇이 효율적인지 아닌지 개선하고 이해할 수있는 곳을보고 싶습니다.
public class Duplicate {
public static void main (String [] args){
// filter duplicate elements
int [] arr = {5,4,3,5,4,6,7,8,6};
Arrays.sort(arr);
int length = arr.length;
List<Integer> list = new ArrayList<>();
list.add(arr[0]);
for(int i =0; i <length-1;i++){
if(arr[i] != arr[i+1]){
list.add(arr[i+1]);
}
}
System.out.println(Arrays.toString(list.toArray()));
}
}
답변1
int [] arr = {5, 4, 3, 5, 4, 6, 7, 8, 6};
Set<Integer> set = new HashSet<>();
int length = arr.length;
for(int i = 0; i < length; i++){
set.add(arr[i]);
}
System.out.println(Arrays.toString(set.toArray()));
답변2
예를 들어 원래 순서가 중요하거나 요소를 정렬 가능한 방식으로 비교할 수없는 경우와 같이 정렬하지 않고 해결책을 찾을 수있는 것이 면접관에게 중요 할 수 있습니다 (면접 질문의 전체 컨텍스트를 모르겠습니다). .O (n ^ 2) 시간이 걸리지 만 순서를 유지하고 O (1) 공간을 차지하는 솔루션은 요소별로 이동하고 나머지 데이터 구조에서 현재 요소의 반복을 검색하고 제거하는 것입니다.연결 목록과 같이 O (1) 제거가 포함 된 구조를 사용하면 O (n ^ 2)가 필요합니다.
답변3
이 문제는 입력에 대한 제약이 무엇인지 아는 한 몇 줄의 코드만으로 매우 간단합니다.
int [] arr = {5,4,3,5,4,6,7,8,6};
int maxPossibleInputValue = 9;
...
List<Integer> list = new ArrayList<>();
byte[] tracker = new byte[maxPossibleInputValue + 1];
for (int i = 0; i < arr.length; i++)
{
if (tracker[arr[i]]++ == 0)
{
list.add(arr[i]);
}
}
즉
List<Integer> mainRoutine(int[] arr)
{
List<Integer> list = new ArrayList<>();
MyNode[] tracker = new MyNode[65536];
for (int i = 0; i < arr.length; i++)
{
int segment = arr[i] % tracker.length;
if (tracker[segment] == null) || !tracker[segment].has(arr[i]))
{
list.add(arr[i]);
}
MyNode newNode = new MyNode(arr[i], tracker[segment]);
tracker[segment] = newNode;
}
return list;
}
...
...
private static class MyNode
{
private final int val;
private MyNode child;
private MyNode(int val, MyNode child)
{
this.val = val;
this.child = child;
}
boolean has(int val)
{
return (this.val == val) || (child != null && child.has(val);
}
}
