当前位置:网站首页>leetcode每日一题:字符串中的第一个唯一字符
leetcode每日一题:字符串中的第一个唯一字符
2022-07-05 17:17:00 【利刃Cc】
链接:字符串中的第一个唯一字符
(注:该题提示字符串只包含小写字母)
常规思路:对每个字符都进行一次遍历,查找是否字符串中是否有相同的字母。(但是最坏情况下时间复杂度为O(n^2),所以这里不推荐)
代码:
class Solution {
public:
int firstUniqChar(string s) {
//常规思路:每次都遍历查找是否有相等的,时间复杂度O(n^2),不推荐
for(size_t i = 0; i < s.size(); i++)
{
//用flag用做标记,若变为0说明有相同的
int flag = 1;
for(size_t j = 0; j < s.size(); j++)
{
//若下标相同则不需要对比
if(j == i)
continue;
if(s[j] != s[i])
continue;
else
{
flag = 0;
break;
}
}
if(flag == 1)
return i;
}
return -1;
}
};
另一种思路: 使用计数排序的思想,统计字符串中每个字母出现的次数,然后再将第一个计数数组中为1的字母返回。
注:该思路的时间复杂度为O(N)。
代码:
class Solution {
public:
int firstUniqChar(string s) {
// 时间复杂度为O(n)
// 利用计数排序的思想,先统计每个字母出现的次数
int arr[26] = {
0};
for(size_t i = 0; i < s.size(); i++)
{
arr[s[i] - 'a']++;
}
//查找s中对应arr出现的次数是否为一次
for(size_t i = 0; i < s.size(); i++)
{
if(arr[s[i] - 'a'] == 1)
return i;
}
return -1;
}
};
边栏推荐
- 如何修改mysql字段为自增长字段
- Is it safe and reliable to open futures accounts on koufu.com? How to distinguish whether the platform is safe?
- Mysql5.6 parsing JSON strings (supporting complex nested formats)
- 2022年信息系统管理工程师考试大纲
- Troubleshooting - about clip not found Visual Studio
- 漫画:寻找无序数组的第k大元素(修订版)
- 基于51单片机的电子时钟设计
- 华为云云原生容器综合竞争力,中国第一!
- 机器学习02:模型评估
- C#实现水晶报表绑定数据并实现打印3-二维码条形码
猜你喜欢
MySQL之知识点(六)
7. Scala class
Oracle Recovery Tools ----oracle数据库恢复利器
CVPR 2022 best student paper: single image estimation object pose estimation in 3D space
Compter le temps d'exécution du programme PHP et définir le temps d'exécution maximum de PHP
一文了解MySQL事务隔离级别
IDEA 项目启动报错 Shorten the command line via JAR manifest or via a classpath file and rerun.
Winedt common shortcut key modify shortcut key latex compile button
To solve the problem of "double click PDF file, pop up", please install Evernote program
ICML 2022 | Meta提出鲁棒的多目标贝叶斯优化方法,有效应对输入噪声
随机推荐
一文读懂简单查询代价估算
机器学习02:模型评估
外盘黄金哪个平台正规安全,怎么辨别?
关于mysql中的json解析函数JSON_EXTRACT
CVPR 2022 best student paper: single image estimation object pose estimation in 3D space
The five most difficult programming languages in the world
Learn about MySQL transaction isolation level
IDC报告:腾讯云数据库稳居关系型数据库市场TOP 2!
请问下为啥有的表写sql能查到数据,但在数据地图里查不到啊,查表结构也搜不到
Check the WiFi password connected to your computer
Summary of optimization scheme for implementing delay queue based on redis
提高應用程序性能的7個DevOps實踐
【二叉树】根到叶路径上的不足节点
Count the running time of PHP program and set the maximum running time of PHP
Server configuration jupyter environment
winedt常用快捷键 修改快捷键latex编译按钮
Cartoon: interesting pirate problem (full version)
Seven Devops practices to improve application performance
Cartoon: how to multiply large integers? (integrated version)
机器学习01:绪论