删除数组中的重复项（保留最后一次出现的重复元素并保证数组的原有顺序）

小半 • 2023年2月3日上午10:51 • 技术随笔 • 阅读 206

链接
第21题；

方法一：Set判断是否重复 + list存正确的元素

逆序遍历，不重复则添加至list；
使用Collections.reverse() 将list倒置；
将list放入int[ ]数组；

public int[] removeDuplicate (int[] array) {
        // write code here
        HashSet<Integer> s=new HashSet<>();
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=array.length-1;i>=0;i--){
            if(!s.contains(array[i])){
                s.add(array[i]);
                list.add(array[i]);
            }
        }
        // 倒置list
        Collections.reverse(list);
        // list到int数组 ！
        int j=0;
        int[] r=new int[list.size()];
        for(int k:list){
            r[j++]=k;
        }
        return r;
    }
}

结果： 通过全部用例

将list变成int[]数组的两种方式：

使用 j 作为数组索引，用foreach将list遍历给 r[j]

		int j=0;
        int[] r=new int[list.size()];
        for(int k:list){
            r[j++]=k;
        }

Collection接口的toArray方法，返回Object数组，遍历转型为int

		Object[] r = list.toArray();
        int[] r1=new int[list.size()];
        for(int i=0;i<list.size();i++){
            r1[i]=(int)r[i];
        }

方法二：逆序遍历时添加至linkedHashSet（重复的值不会再添加！）

linkedHashSet后面再插入相同的值不会覆盖掉前面的值！

    public int[] removeDuplicate (int[] array) {
        LinkedHashSet<Integer> h=new LinkedHashSet<>();
        for(int i=array.length-1;i>=0;i--){
            h.add(array[i]);
        }
        Iterator<Integer> iterator = h.iterator();
        ArrayList<Integer> list=new ArrayList<>();
        for(int k:h){
            list.add(k);
        }
        Collections.reverse(list);
        int[] r=new int[list.size()];
        int index=0;
        for(int k:list){
            r[index++]=k;
        }
        for(int k:r){
            System.out.print(k);
        }
        return r;
    }

结果： 通过全部用例

方法三：栈判断是否重复，正确则压栈

逆向遍历，遍历时用contain方法判断是否已存在；（Stack继承于Vector类；Vector实现了Iterable和Collection接口）
接收再弹出给新的数组，最后返回新数组；
结果： 通过6/8，运行超时

    public int[] removeDuplicate (int[] array) {
        // 暴力
        //最后一次出现，那就逆向遍历
        Stack<Integer> s=new Stack<>();
        for(int i=array.length-1;i>=0;i--){
            if(!s.contains(array[i])){
                s.push(array[i]);
            }
        }
        //放入新数组
        int n=s.size();
        int[] r=new int[n];
        //弹栈，正好顺序颠倒过来
        for(int j=0;j<n;j++){
            r[j]=s.pop();
        }
        return r;
    }

方法四：Set判断是否重复 + 快慢指针

先逆序遍历，使用Set判断是否重复，重复就置为0；
使用快慢指针删除0；
将长度为slow的所有元素放至新数组并返回；

public int[] removeDuplicate (int[] array) {
        int n=array.length;
        Set<Integer>  s=new HashSet<>();
        // 倒序遍历，将重复的置为0
        for(int i=n-1;i>=0;i--){
            if(s.contains(array[i])){
               array[i]=0;
            }else{
               s.add(array[i]);
            }
        }

        // 快慢指针删除数组中的0
        int slow=0;
        int fast=0;
        while(fast<n){
            if(array[fast]==0){
                fast++;
            }else{
                array[slow]=array[fast];
                slow++;
                fast++;
            }
        }

        //0~slow移到新数组
        int[] r=new int[slow];
        for(int i=0;i<slow;i++){
            r[i]=array[i];
        }
        return r;
    }