791. Custom Sort String
2022/1/14 6:04:41
本文主要是介绍791. Custom Sort String,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一拿到这道题,我首先想的是用binary search做,但是因为结果String的长度不是固定的,用binary search很难实现。所以我写了第一个brute force的算法,时间复杂度是O(n2), 效率很低,beat 5%,而且很容易考虑不到edge case而出错。
Map<Character, Integer> map = new HashMap<>(); public String customSortString(String order, String s) { for (int i = 0; i < order.length(); i++) { map.put(order.charAt(i), i); } StringBuilder res = new StringBuilder(); res.append(s.charAt(0)); for (int i = 1; i < s.length(); i++) { char c = s.charAt(i); if (!map.containsKey(c)) res.append(c); else search(res, c, map); } return res.toString(); } private void search(StringBuilder s, char c, Map<Character, Integer> map) { for (int i = 0; i < s.length(); i++) { char temp = s.charAt(i); if (!map.containsKey(temp) || map.get(temp) < map.get(c)) continue; else if (map.get(temp) >= map.get(c)) { s.insert(i, c); return; } } s.append(c); }
这道题是求字符串里的对字符的sort,我们还可以利用bucket sort来做,首选把s放在bucket,再用order做sort,最后再把那些没有在order里面的字符加到字符串上即可,时间复杂度O(n), 算法如下:
public String customSortString_bucketsort(String order, String s) { int[] bucket = new int[26]; for (int i = 0; i < s.length(); i++) { int c = s.charAt(i); bucket[c - 'a']++; } StringBuilder res = new StringBuilder(); for (int i = 0; i < order.length(); i++) { int index = order.charAt(i) - 'a'; for (int j = 0; j < bucket[index]; j++) { res.append((char) (index + 'a')); } bucket[index] = 0; } for (int i = 0; i < bucket.length; i++) { for (int j = 0; j < bucket[i]; j++) { res.append((char) (i + 'a')); } } return res.toString(); }
这篇关于791. Custom Sort String的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享