【算法题】面试题 01.01. 判定字符是否唯一

绝地灬酷狼 2023-10-12 13:30 56阅读 0赞

> **题目来源：[《程序员面试金典（第 6 版）》][6]**
> 
> > 1、Problem: [面试题 01.01. 判定字符是否唯一][01.01.]

### 文章目录 ###

*  面试题 01.01. 判定字符是否唯一
 *   *  一、题目描述
     *  二、解决方案
     *   *  （一）方案一
         *   *   *  1、解题思路
                 *  2、解题方法
                 *  3、复杂度
                 *  4、代码实现
         *  （二）方案二
         *   *   *  1、思路
                 *  2、解题方法
                 *  3、复杂度
                 *  4、Code
         *  （三）方案三
         *   *   *  1、思路
                 *  2、解题方法
                 *  3、复杂度
                 *  4、Code
     *  三、测试验证

# 面试题 01.01. 判定字符是否唯一 #

## 一、题目描述 ##

![在这里插入图片描述][c21c7022f09d4a80a4927a8ca2825886.png]

## 二、解决方案 ##

### （一）方案一 ###

##### 1、解题思路 #####

1.  第一轮遍历：从第一个字符开始，依次与后面的所有字符作比较。如果存在相同就直接返回false，退出循环；如果不存在相同，则继续进行第二轮遍历。
2.  第二轮遍历：从第二个字符开始，依次与后面的所有字符作比较。
3.  第三轮遍历：从第三个字符开始，依次与后面的所有字符作比较。
4.  依次类推，直至完成第n-1轮遍历。

##### 2、解题方法 #####

使用双重循环进行遍历求解。

##### 3、复杂度 #####

*  时间复杂度:  O ( n 2 ) O(n^2) O(n2)
 *  空间复杂度:  O ( n ) O(n) O(n)

##### 4、代码实现 #####

class Solution {
        
        public boolean isUnique(String astr) {
        
            for(int i=0; i<astr.length()-1; i++) {
        
                char ch = astr.charAt(i);
                for(int j=i+1; j<astr.length(); j++) {
        
                    if(ch == astr.charAt(j)) {
        
                        return false;
                    }
                }
            }
            return true;
        }
    }

### （二）方案二 ###

##### 1、思路 #####

使用 HashMap 来存放字符，并统计字符个数，当字符个数大于1时，表示存在字符重复，直接返回 false。当遍历完字符串中所有的字符后，仍没有重复字符出现，则返回 true。

##### 2、解题方法 #####

使用 HashMap 来存放字符并统计字符个数。

##### 3、复杂度 #####

*  时间复杂度:  O ( n ) O(n) O(n)
 *  空间复杂度:  O ( n ) O(n) O(n)

##### 4、Code #####

class Solution {
        
        public boolean isUnique(String astr) {
        
            Map<Character, Integer> map = new HashMap();
            for(int i=0; i<astr.length(); i++) {
        
                char ch = astr.charAt(i);
                if(map.get(ch) == null || map.get(ch) == 0) {
        
                    map.put(ch, 1);
                } else {
        
                    map.put(ch, map.get(ch)+1);
                }
                if(map.get(ch) > 1) {
        
                    return false;
                }
            }
            return true;
        }
    }

### （三）方案三 ###

##### 1、思路 #####

构造一个布尔值的数组，索引值 i 对应的标记指示该字符串是否含有字符表第 i 个字符。

##### 2、解题方法 #####

布尔值的数组。

##### 3、复杂度 #####

*  时间复杂度:  O ( n ) O(n) O(n)
 *  空间复杂度:  O ( 1 ) O(1) O(1)

##### 4、Code #####

/**
     * 构造一个布尔值的数组，索引值 i 对应的标记指示该字符串是否含有字符表第 i 个字符。
     */
    class Solution {
        
        public boolean isUnique(String astr) {
        
            if(astr.length() > 128) {
         // 如果字符串的长度超过了字母表中不同字符的个数，则直接返回false
                return false;
            }
    
            boolean[] char_set = new boolean[128];
            for(int i=0; i<astr.length(); i++) {
        
                int val = astr.charAt(i); 
                if(char_set[val]) {
         // 在字符串中已找到该字符
                    return false;
                }
                char_set[val] = true;
            }
            return true;
        }
    }

## 三、测试验证 ##

> **方案一：**  
> ![在这里插入图片描述][eab45fc3805d4e9790df4c7bdd6acc53.png]

> **方案二：**  
> ![在这里插入图片描述][4f4ff04dc70745a5baf88d0640b22c2c.png]

> **方案三：**![在这里插入图片描述][73e5380f8bf5463d839cf90c73fddf1b.png]

[6]: https://leetcode.cn/studyplan/cracking-the-coding-interview/
[01.01.]: https://leetcode.cn/problems/is-unique-lcci/description/
[c21c7022f09d4a80a4927a8ca2825886.png]: https://img-blog.csdnimg.cn/c21c7022f09d4a80a4927a8ca2825886.png
[eab45fc3805d4e9790df4c7bdd6acc53.png]: https://img-blog.csdnimg.cn/eab45fc3805d4e9790df4c7bdd6acc53.png
[4f4ff04dc70745a5baf88d0640b22c2c.png]: https://img-blog.csdnimg.cn/4f4ff04dc70745a5baf88d0640b22c2c.png
[73e5380f8bf5463d839cf90c73fddf1b.png]: https://img-blog.csdnimg.cn/73e5380f8bf5463d839cf90c73fddf1b.png