编写一个高效的程序来打印输入字符串中的所有副本及其计数
null
方法1： 使用哈希 算法： 让输入字符串为“Geeksforgeks” 1: 从输入字符串构造字符计数数组。 计数[‘e’]=4 计数[‘g’]=2 计数[‘k’]=2 …… 2: 打印构造的数组中值大于1的所有索引。 解决方案
C++14
// C++ program to count all duplicates // from string using hashing #include <iostream> using namespace std; # define NO_OF_CHARS 256 class gfg { public : /* Fills count array with frequency of characters */ void fillCharCounts( char *str, int *count) { int i; for (i = 0; *(str + i); i++) count[*(str + i)]++; } /* Print duplicates present in the passed string */ void printDups( char *str) { // Create an array of size 256 and fill // count of every character in it int *count = ( int *) calloc (NO_OF_CHARS, sizeof ( int )); fillCharCounts(str, count); // Print characters having count more than 0 int i; for (i = 0; i < NO_OF_CHARS; i++) if (count[i] > 1) printf ( "%c, count = %d " , i, count[i]); free (count); } }; /* Driver code*/ int main() { gfg g ; char str[] = "test string" ; g.printDups(str); //getchar(); return 0; } // This code is contributed by SoM15242 |
C
// C program to count all duplicates // from string using hashing # include <stdio.h> # include <stdlib.h> # define NO_OF_CHARS 256 /* Fills count array with frequency of characters */ void fillCharCounts( char *str, int *count) { int i; for (i = 0; *(str+i); i++) count[*(str+i)]++; } /* Print duplicates present in the passed string */ void printDups( char *str) { // Create an array of size 256 and // fill count of every character in it int *count = ( int *) calloc (NO_OF_CHARS, sizeof ( int )); fillCharCounts(str, count); // Print characters having count more than 0 int i; for (i = 0; i < NO_OF_CHARS; i++) if (count[i] > 1) printf ( "%c, count = %d " , i, count[i]); free (count); } /* Driver program to test to print printDups*/ int main() { char str[] = "test string" ; printDups(str); getchar (); return 0; } |
JAVA
// Java program to count all // duplicates from string using // hashing public class GFG { static final int NO_OF_CHARS = 256 ; /* Fills count array with frequency of characters */ static void fillCharCounts(String str, int [] count) { for ( int i = 0 ; i < str.length(); i++) count[str.charAt(i)]++; } /* Print duplicates present in the passed string */ static void printDups(String str) { // Create an array of size // 256 and fill count of // every character in it int count[] = new int [NO_OF_CHARS]; fillCharCounts(str, count); for ( int i = 0 ; i < NO_OF_CHARS; i++) if (count[i] > 1 ) System.out.println(( char )(i) + ", count = " + count[i]); } // Driver Method public static void main(String[] args) { String str = "test string" ; printDups(str); } } |
python
# Python program to count all # duplicates from string using hashing NO_OF_CHARS = 256 # Fills count array with # frequency of characters def fillCharCounts(string, count): for i in string: count[ ord (i)] + = 1 return count # Print duplicates present # in the passed string def printDups(string): # Create an array of size 256 # and fill count of every character in it count = [ 0 ] * NO_OF_CHARS count = fillCharCounts(string,count) # Utility Variable k = 0 # Print characters having # count more than 0 for i in count: if int (i) > 1 : print chr (k) + ", count = " + str (i) k + = 1 # Driver program to test the above function string = "test string" print printDups(string) # This code is contributed by Bhavya Jain |
C#
// C# program to count all duplicates // from string using hashing using System; class GFG { static int NO_OF_CHARS = 256; /* Fills count array with frequency of characters */ static void fillCharCounts(String str, int [] count) { for ( int i = 0; i < str.Length; i++) count[str[i]]++; } /* Print duplicates present in the passed string */ static void printDups(String str) { // Create an array of size 256 and // fill count of every character in it int []count = new int [NO_OF_CHARS]; fillCharCounts(str, count); for ( int i = 0; i < NO_OF_CHARS; i++) if (count[i] > 1) Console.WriteLine(( char )i + ", " + "count = " + count[i]); } // Driver Method public static void Main() { String str = "test string" ; printDups(str); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to count // all duplicates from // string using hashing function fillCharCounts( $str , $count ) { for ( $i = 0; $i < strlen ( $str ); $i ++) $count [ord( $str [ $i ])]++; for ( $i = 0; $i < 256; $i ++) if ( $count [ $i ] > 1) echo chr ( $i ) . ", " . "count = " . ( $count [ $i ]) . "" ; } // Print duplicates present // in the passed string function printDups( $str ) { // Create an array of size // 256 and fill count of // every character in it $count = array (); for ( $i = 0; $i < 256; $i ++) $count [ $i ] = 0; fillCharCounts( $str , $count ); } // Driver Code $str = "test string" ; printDups( $str ); // This code is contributed by Sam007 ?> |
Javascript
<script> // Javascript program to count all duplicates // from string using hashing let NO_OF_CHARS = 256; /* Print duplicates present in the passed string */ function printDups(str) { // Create an array of size 256 and // fill count of every character in it let count = new Array(NO_OF_CHARS); count.fill(0); for (let i = 0; i < str.length; i++) count[str[i].charCodeAt()]++; for (let i = 0; i < NO_OF_CHARS; i++) { if (count[i] > 1) { document.write(String.fromCharCode(i) + ", " + "count = " + count[i] + "</br>" ); } } } let str = "test string" ; printDups(str); </script> |
输出
s, count = 2 t, count = 3
时间复杂性： O（n），其中n=所传递字符串的长度
空间复杂性 ：O（无字符）
注： 哈希涉及每次使用固定大小的数组，无论字符串是什么。
例如，str=“aaaaaaaaaa”。
大小为256的数组用于str，总大小（256）中只有1个块将用于存储str中出现“a”的次数（即计数[‘a’]=10）。
剩余256–1=255个块未使用。
因此，在这种情况下，空间复杂度可能很高。因此，为了避免任何差异并提高空间复杂度，与长尺寸阵列相比，地图通常更受欢迎。
方法2： 使用地图
方法： 该方法与中讨论的方法相同 方法1 ，但是，使用地图存储计数。
解决方案：
C++
// C++ program to count all duplicates // from string using maps #include <bits/stdc++.h> using namespace std; void printDups(string str) { map< char , int > count; for ( int i = 0; i < str.length(); i++) { count[str[i]]++; } for ( auto it : count) { if (it.second > 1) cout << it.first << ", count = " << it.second << "" ; } } /* Driver code*/ int main() { string str = "test string" ; printDups(str); return 0; } // This code is contributed by yashbeersingh42 |
JAVA
// Java program to count all duplicates // from string using maps import java.util.*; class GFG { static void printDups(String str) { HashMap<Character, Integer> count = new HashMap<>(); /*Store duplicates present in the passed string */ for ( int i = 0 ; i < str.length(); i++) { if (!count.containsKey(str.charAt(i))) count.put(str.charAt(i), 1 ); else count.put(str.charAt(i), count.get(str.charAt(i)) + 1 ); } /*Print duplicates in sorted order*/ for (Map.Entry mapElement : count.entrySet()) { char key = ( char )mapElement.getKey(); int value = (( int )mapElement.getValue()); if (value > 1 ) System.out.println(key + ", count = " + value); } } // Driver code public static void main(String[] args) { String str = "test string" ; printDups(str); } } // This code is contributed by yashbeersingh42 |
蟒蛇3
# Python 3 program to count all duplicates # from string using maps from collections import defaultdict def printDups(st): count = defaultdict( int ) for i in range ( len (st)): count[st[i]] + = 1 for it in count: if (count[it] > 1 ): print (it, ", count = " , count[it]) # Driver code if __name__ = = "__main__" : st = "test string" printDups(st) # This code is contributed by ukasp. |
C#
// C# program to count all duplicates // from string using maps using System; using System.Collections.Generic; using System.Linq; class GFG{ static void printDups(String str) { Dictionary< char , int > count = new Dictionary< char , int >(); for ( int i = 0; i < str.Length; i++) { if (count.ContainsKey(str[i])) count[str[i]]++; else count[str[i]] = 1; } foreach ( var it in count.OrderBy(key => key.Value)) { if (it.Value > 1) Console.WriteLine(it.Key + ", count = " + it.Value); } } // Driver code static public void Main() { String str = "test string" ; printDups(str); } } // This code is contributed by shubhamsingh10 |
Javascript
<script> //Javascript Implementation // to count all duplicates // from string using maps function printDups(str) { var count = {}; for ( var i = 0; i < str.length; i++) { count[str[i]] = 0; } for ( var i = 0; i < str.length; i++) { count[str[i]]++; } for ( var it in count) { if (count[it] > 1) document.write(it + ", count = " + count[it] + "<br>" ); } } /* Driver code*/ var str = "test string" ; printDups(str); // This code is contributed by shubhamsingh10 </script> |
输出
s, count = 2t, count = 3
时间复杂性 ：O（N logN），其中N=传递的字符串的长度，在映射中插入元素通常需要logN时间。
空间复杂性 ：O（K），其中K=地图的大小( 0<=K<=输入字符串长度 ).
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
C++
// C++ program to count all duplicates // from string using maps #include <bits/stdc++.h> using namespace std; void printDups(string str) { unordered_map< char , int > count; for ( int i = 0; i < str.length(); i++) { count[str[i]]++; //increase the count of characters by 1 } for ( auto it : count) { //iterating through the unordered map if (it.second > 1) //if the count of characters is greater then 1 then duplicate found cout << it.first << ", count = " << it.second << "" ; } } /* Driver code*/ int main() { string str = "test string" ; printDups(str); return 0; } |
输出
s, count = 2t, count = 3
时间复杂性：
O（N），其中N=传递的字符串的长度，插入和访问无序映射中的任何元素需要O（1）时间
空间复杂性：
O（K），其中K=映射的大小（0<=K<=input_string_length）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
