本文共 2224 字，大约阅读时间需要 7 分钟。

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

题目链接：

使用hashmap(该方法并不好，当数据量很多的时候，内存占用特别大)：

// 基本方法，并非最优，但是大多数人都是这个方法import java.util.HashMap;public class Solution {    public int FirstNotRepeatingChar(String str) {        if (str == null || str.length() == 0)    return -1;        HashMap
   
     map = new HashMap<>();        int len = str.length();        char c;        for (int i = 0; i < len; ++i) {            c = str.charAt(i);            if (map.containsKey(c)) {                map.put(c, map.get(c) + 1);            } else {                map.put(c, 1);            }        }        for (int i = 0; i < len; ++i) {            if (map.get(str.charAt(i)) == 1) {                return i;            }        }        return -1;    }}
   

使用位图方法：

关于位图基本理解可以随便上网搜，比如这一篇，或者找其他的也行。

也可以查看BitSet源码，源码的<<循环移位很巧妙，不用求余运算，不过只是处理数据是否存在，而不是处理存在了一次或者多次的，所以不能直接用BitSet。

public class Solution {    final int ARRAYNUM = 10001 >> 4;//10001 * 2 / 32    final int[] arr = new int[ARRAYNUM];    public int FirstNotRepeatingChar(String str) {        char[] charArray = str.toCharArray();        int len = charArray.length;        for (int i = 0; i < len; ++i) {            set(charArray[i]);        }        for (int i = 0; i < len; ++i) {            if (get(charArray[i]) == 1) {                return i;            }        }        return -1;    }    private int get(char bitIndex) {        int wordIndex = bitIndex >> 4; // 数据项，bitIndex / 16,每个int元素可以表示16个字符，每个字符三种状态00未出现，01一次，10多次，2个bit位即可        int pos = (bitIndex & 31) << 1; // 偏移量，除以32的余数，每个数据项占2bit位，所以乘以2        int temp = (arr[wordIndex] >> pos) & 0x03;        return temp;    }     private void set(char bitIndex) {        int wordIndex = bitIndex >> 4; // 数据项，bitIndex / 16,每个int元素可以表示16个字符，每个字符三种状态00未出现，01一次，10多次，2个bit位即可        int pos = (bitIndex & 31) << 1; // 偏移量，除以32的余数，每个数据项占2bit位，所以乘以2        int temp = (arr[wordIndex] >> pos) & 0x03;        ++temp;        if (temp >= 2)  temp = 2;        if (temp == 2) { // 为2说明已经出现过一次，本次是重复的            arr[wordIndex] &= ~(0x03 << pos); // 先清空        }        // 为1说明字符未出现过，本次为第一次        arr[wordIndex] |= temp << pos; // 赋值    }}

==============Talk is cheap, show me the code==============

转载地址：https://liuchenyang0515.blog.csdn.net/article/details/86688125 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！