Java教程

数组/链表高效去重(算法题

本文主要是介绍数组/链表高效去重(算法题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

有序数组/链表去重

对于数组相关的算法题,有一个通用的技巧:要尽量避免在中间删除元素,那我就先想办法把这个元素换到最后去。这样的话,最终待删除的元素都拖在数组尾部,一个一个 pop 掉就行了,每次操作的时间复杂度也就降低到 O(1) 了。

按照上面的思路可以使用双指针的方法,我们让慢指针slow走左后面,快指针fast走在前面探路,找到一个不重复的元素就告诉slow并让slow前进一步。

这样当fast指针遍历完整个数组nums后,nums[0..slow]就是不重复元素,之后的所有元素都是重复元素

字母去重

最后做一道算是去重算法题中难度最大的,把这题搞懂去重部分的算法题应该就没问题了。

LeetCode 316 字母去重

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

题目要求总结有三:

  1. 去重

  2. 不能打算输入字符串s中的字符出现的相对顺序

  3. 在符合前面两条的情况下,选出字典序最小的作为最终结果。

思路

  1. 通过使用布尔数组inStack来做到栈stk中不存在重复元素

  2. 顺序遍历字符串s,通过「栈」这种顺序结构的 push/pop 操作记录结果字符串,保证了字符出现的顺序和s中出现的顺序一致。

  3. 利用单调栈的思路以及使用计数器count来不断pop掉不符合最小字典序的字符。

class Solution {
    public String removeDuplicateLetters(String s) {
        //存放去重结果
        Stack<Character> stk = new Stack<>();
​
        int[] count = new int[256];
        for(int i=0;i<s.length();i++){
            count[s.charAt(i)]++;
        }
​
        boolean[] inStack = new boolean[256];
        for(char c:s.toCharArray()){
            count[c]--;
​
            if(inStack[c]) continue;
​
            while(!stk.isEmpty()&&stk.peek()>c){
                if(count[stk.peek()]==0){
                    break;
                }
                inStack[stk.pop()] = false;
            }
            stk.push(c);
            inStack[c] = true;
        } 
​
        StringBuilder sb = new StringBuilder();
        while(!stk.isEmpty()){
            sb.append(stk.pop());
        }
        //由于栈是先进后出的,所以要反转一次才是最终结果
        return sb.reverse().toString();
    }
}

 

 

 

这篇关于数组/链表高效去重(算法题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!