Leetcode442.java

packagecom.company;

importjava.util.*;

publicclassLeetcode442 {
publicstaticvoidmain(String[] args) {
intarr[]={4,3,2,7,8,2,3,1};
List<Integer> ans=duplicate(arr);
System.out.println(ans);
 }


staticList<Integer> duplicate(int[] arr){
inti=0;
while(i<arr.length){
intcorrectIndex=arr[i]-1;
if(arr[i]!=arr[correctIndex]){
swap(arr,i,correctIndex);
 }
else {
i++;
 }
 }

List<Integer> ans=newArrayList<>();
for(intj=0;j<arr.length;j++){
if(arr[j]!=j+1){
ans.add(arr[j]);
 }
 }

returnans;
 }

staticvoidswap(int[] arr, inta, intb){
inttemp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
 }
}