算法-如何查找第一个只出现一次的字符

2020-07-27  本文已影响0人  zzq_nene

方式一:

遍历每一个字符,然后取出遍历的当前字符与剩下的字符做比较,判断剩下的字符串中是否有当前遍历的这个字符,如果没有,则是在字符串中出现一次的,而第一个出现的,就是要查找的。

    /**
     * 使用便利的方式,时间复杂度是O(n^2)
     * @param str
     */
    private static void printFirstCharOnlyOnce(String str) {
        for (int i = 0; i < str.length(); i++) {
            // 截去第i个字符
            String temp = str.substring(0, i) + str.substring(i + 1);
            // 判断截去第i个字符后剩下的字符串中是否还有与第i个字符相同的字符
            int index = temp.indexOf(str.charAt(i));
            // 如果剩下的字符中没有与第i个字符相同的字符存在,则返回-1
            // 第一次出现index=-1的时候,说明第i个字符就是第一个出现一次的字符
            if (index == -1) {
                String c = String.valueOf(str.charAt(i));
                System.out.println(c);
                break;
            }
        }
    }

方式二:

直接使用hash表来查询,即使用HashMap来实现;首先遍历字符串的每一个字符,将字符作为HashMap的key,然后使用Integer作为HashMap的value,当key相同的时候,value就加1。遍历完之后,再对HashMap做遍历,找出key对应的value=1的key,第一个key就是查找第一个只出现一次的字符

    /**
    * 时间复杂度为O(n)
    */
    private static void printFirstCharOnlyOnce(String str) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            if (hashMap.containsKey(str.charAt(i))) {
                int value = hashMap.get(str.charAt(i));
                hashMap.put(str.charAt(i), value + 1);
            } else {
                hashMap.put(str.charAt(i), 1);
            }
        }

        for (int i = 0; i < str.length(); i++) {
            if (hashMap.get(str.charAt(i)) == 1) {
                System.out.println(str.charAt(i));
                break;
            }
        }
    }

方式三:

借助ASCII码,将字符的ASCII码作为在int数组的索引位置,而该字符出现的次数就是对应的int数组的索引位置的值

    private static void printFirstCharOnlyOnce(String str) {
        int[] hash = new int[256];
        for (int i = 0; i < str.length(); i++) {
            int temp = str.charAt(i);
            hash[temp]++;
        }

        for (int i=0;i<str.length();i++) {
            int temp = str.charAt(i);
            if (hash[temp] == 1) {
                System.out.println(str.charAt(i));
                break;
            }
        }
    }
上一篇 下一篇

猜你喜欢

热点阅读