字符串中的第一个唯一字符 Python

2024 年 8 月 29 日 | 阅读 6 分钟

本教程将展示查找给定字符串的第一个唯一字符的各种方法。例如，如果给定字符串是“stringstutorial”，则结果应为“n”，如果给定字符串是“StringsTutorial”，则结果应为“S”。

说明

输入：“stringstutorial”

说明

步骤 1：为给定字符串创建字符频率列表

freq['s'] = 2

freq['t'] = 3

freq['r'] = 2

freq['i'] = 2

freq['n'] = 1

freq['g'] = 1

freq['u'] = 1

freq['o'] = 1

freq['a'] = 1

freq['l'] = 1

步骤 2：查找频率为单位的第一个字符。

创建频率哈希图

如果一个字符在给定字符串中只出现一次，则认为它是非重复字符。定位此类唯一字符的步骤是计算字符串序列中每个字母的频率，并确定哪个字母的频率为 1。哈希图是一种有效的工具，它可以将字符映射到其对应的频率，使我们能够以恒定的时间同时修改我们已经遇到的字符的频率。在 ASCII 系统中，256 个唯一字符是限制。因此，哈希图的最大长度为 256。重新读取字符串，频率等于一的第一个字母就是答案。

算法

创建一个哈希图，将每个字符与其频率关联起来。
使用指针遍历输入字符串。
修改哈希图中当前存在的字符数量。
接下来，再次遍历字符串，确定当前字符的频率是否为 1。
如果频率大于 1，则继续遍历。
否则，结束循环并将当前字符输出为答案。

代码

# Python implementation of the hash map algorithm to find the first unique character

max_chars = 256

# Defining a function to give a list of length 256 containing the frequency of the characters of the string
def CharFreq(string):
    freq = [0] * max_chars
    # Iterating over the string and updating the frequency
    for _ in string:
        freq[ord(_)] += 1
    return freq

# Defining a function to return the first unique letter of the string
def firstUnique(string):
    freq = CharFreq(string)
    # Initializing index as -1 for no unique character case
    idx = -1
    k = 0

    for _ in string:
        if freq[ord(_)] == 1:
            idx = k
            break
        k += 1

    return idx

# Driver code for the above methods
string = "stringstutorial"
idx = firstUnique(string)
if idx == -1:
    print ("The given string has no unique character or empty string is given")
else:
    print ("The first unique character is", string[idx])

输出

The first unique character is n

仅遍历一次字符串查找唯一字符

主要方法需要 O(n) 的运行时间，尽管我们可以在应用程序中使其更快。计数数组在过程的第一步中通过 O(n) 的运行时间迭代遍历文本来构建。这一步是合理的。但是，第二部分，即我们重放字符串的第一个非重复项，并不是一个好主意。

在实际情况下，字符串通常比我们的字符集长得多。考虑 DNA 序列，它们可能有数十亿个字母，但只有一个四字母字母表。如果唯一字符位于字符串的末尾，会发生什么？然后，它将需要很长的扫描。

创建哈希图并仅遍历字符串一次

不要使用哈希图，而是创建一个长度为 256 的频率数组，该长度等于字符列表的长度。通过向频率数组添加信息，我们可以存储不仅频率，还可以存储字母首次出现的位置，例如字母的 (5, 36)，表示它被记录了五次，最初出现在位置 36。为了找到第一个唯一字符，我们只需要扫描频率数组而不是字符串。下面是这个想法的实现。

代码

# Python program to find the first unique character by traversing only once
import sys

max_chars = 256

# Defining a function to give the index of the first unique letter of the given string
def firstUnique(string):

    listt = [[] for _ in range(max_chars)]
    for _ in range(max_chars):
        listt[_] = [0,0]

    for _ in range(len(string)):
       
listt[ord(string[_])][0] += 1
       
listt[ord(string[_])][1] = _

    # Initialising the result as sys.maxsize for no unique character case
    r = sys.maxsize
    for _ in range(max_chars):
        # If the current character's frequency is one and is present before the current r value, then modify r
        if (listt[_][0] == 1):
            r = min(r, listt[_][1])

    return r

# Driver code for the above function
string = "stringstutorial"
idx = firstUnique(string)
if (idx == sys.maxsize):
    print("The given string has no unique character or empty string is given")
else:
    print("First unique character is ",string[idx])

输出

First unique character is n

创建频率列表并仅循环一次

创建最多 256 个字符的频率列表。我们可以将此列表中的所有项初始化为 -1。我们将迭代字符串中的字符，并检查此特定字符的列表元素是否索引为 1。如果结果为 -1，我们将将其更改为 j；如果结果不是 -1，则表示该字符已被使用；在这种情况下，我们将将其更改为 -2。

所有重复的字符最终都将被更改为 -2，而所有唯一的字符仍将保留它们首次出现的索引。通过迭代所有唯一的字符，我们可以快速找到最小或初始索引。

代码

# Python program to find the first unique character 
import sys

# Creating a function to find the index of the first unique character
# If no character is unique, the function will return -1
def firstUnique(string):
   freq = [-1 for j in range(256)]
   
   # Setting all non-unique elements to -2 and the unique elements store the index at which they occur in the string
   for j in range(len(string)):
   
     if(freq[ord(string[j])] == -1):
       freq[ord(string[j])] = j
     else:
       freq[ord(string[j])] = -2
     
   result = sys.maxsize

   for j in range(256):
     # If the current character does not have the value -1 or -2, then the character must be present only once in the string.
     # So, we will find the minimum index of all characters uniquely present in the string. This value is the index we need.
     if(freq[j] >= 0):
       result = min(result, freq[j])
   
   # if the result remains int_max, that implies there are no unique characters in the string
   if(result == sys.maxsize):
     return -1
   else:
     return result

   # Drivers code for the above method
string = "stringstutorial"
idx = firstUnique(string)

if (firstUnique == -1):
   print("The given string has no unique character, or empty string is given")
else:
   print("The first unique character is "+ str(string[idx]))

输出

The first unique character is n

使用 Python 的内置函数

利用 Counter() 函数确定所有字符的频率。

遍历字符串并查找频率为 1 的元素。打印唯一字符并在此处中断循环。

代码

# Python program to find the first unique character of string using the Counter function of Python
from collections import Counter

# Defining the function to give the unique character
def printUnique(string):

   # Computing frequency of characters using Counter function
   freq = Counter(string)

   # Looping over the string
   for j in string:
     if(freq[j] == 1):
       print("The first unique character is: ", j)
       break

# Drivers code for the above method
string = "stringstutorial"

# Giving the function above string
printUnique(string)

输出

The first unique character is: n

使用字符串的 find() 函数

在当前字母之后，查找每个后续字母。如果返回 -1，则表示该字母只出现一次，即当前索引。

代码

# Python program to find the unique character of string using the find function

def FirstUnique(string):

   for _ in string:

     if (string.find(_,(string.find(_)+1))) == -1:
       print("The first unique character is: ", _)
       break

   return

# Drivers code 

s = 'stringstutorial'

FirstUnique(string)

输出

The first unique character is: n

使用 count() 函数

如果一个字符在字符串中的 count() 为 1，则表示该字符是唯一的且未重复。我们将中断循环并打印找到的第一个唯一字符。

代码

# Python program to find the first unique character of the string using the count() function

string = "stringstutorial"
idx = -1
freq = ""
for _ in string:
   if string.count(_) == 1:
     freq += _
     break
   else:
     idx += 1
if idx == 1:
   print ("The given string has no unique character, or empty string is given")
else:
   print ("The first unique character is", freq)

输出

The first unique character is n

下一个主题使用 Python 创建自己的电影推荐引擎

← 上一个下一个 →

字符串中的第一个唯一字符 Python

说明

创建频率哈希图

仅遍历一次字符串查找唯一字符

创建哈希图并仅遍历字符串一次

创建频率列表并仅循环一次

使用 Python 的内置函数

使用字符串的 find() 函数

使用 count() 函数

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

字符串中的第一个唯一字符 Python

说明

创建频率哈希图

仅遍历一次字符串查找唯一字符

创建哈希图并仅遍历字符串一次

创建频率列表并仅循环一次

使用 Python 的内置函数

使用字符串的 find() 函数

使用 count() 函数

相关帖子

Python 中的 RSME - 均方根误差

Python 中的类装饰器

Python 中的循环技术

Python Tracemalloc 模块

检查二叉树是否为二叉搜索树

如何使用 Python 写入文本文件

10 款 Python 图像处理工具

使用 Python 代码执行 Google 搜索

Python 中的类型转换

Python 上的 ML 应用金融项目

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器