问题分析
（***）编一个程序，定义一个字符串变量，输入字符串，判断有没有连续重复字符出现，统计重复字符出现次数。
例如，aaabccdfff,其中a重复出现二次，c重复出现一次，f重复出现二次，共计字符重复五次。
题干中的要求，连续重复。比如aaabba，那么最后一个a和前面的三个a就不算连续的。
思考
根据以往的排序算法，嵌套两层for循环。
外层循环和内层循环进行比较。
当不相等时，停止计数，并记录下来内层循环的位置，下一次的外层循环从当前记录的位置开始。
例如：
aaabccc
当a=b时，b的下标时3,那么下一次外层循环从b的位置开始,b和的下一个进行比较。
实现
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test3
{
class Program
{
//（***）编一个程序，定义一个字符串变量，输入字符串，判断有没有连续重复字符出现，统计重复字符出现次数。
//例如，aaabccdfff,其中a重复出现二次，c重复出现一次，f重复出现二次，共计字符重复五次。
static void Main(string[] args)
{
string s = Console.ReadLine();
int allCount = 0; //总数量
//int flag = 0; //下标
for (int flag = 0; flag < s.Length; flag++)
{
int count = 0; //单次数量
for (int j = flag + 1; j < s.Length; j++)
{
if (s[flag] == s[j])
++count;
else
{
break;
}
}
Console.WriteLine((char)s[flag] + ":" + count);
allCount += count;
flag += count;
}
Console.WriteLine("total:" + allCount);
}
}
}
换一种思路
上述题目中使用了两层for循环，是因为当初只考虑了当前的元素和后面所有的元素比较，一直到不相等为止。
现在换一种思路，两两比较，这样只需要一层循环即可：
例如,aaabbccfff,
第一轮:
array[0] array[1]比较相等
第二轮:
array[1] array[2]比较相等
第三轮:
array[2] array[3] 比较不相等，结束计数，计数器清零。
第四轮：
array[3] array[4] 比较相等
第五轮
array[4] array[5] 比较不相等，结束计数，计数器清零。
....
另一种思路的实现
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test3
{
class Program
{
//（***）编一个程序，定义一个字符串变量，输入字符串，判断有没有连续重复字符出现，统计重复字符出现次数。
//例如，aaabccdfff,其中a重复出现二次，c重复出现一次，f重复出现二次，共计字符重复五次。
static void Main(string[] args)
{
string s = Console.ReadLine();
int allCount = 0; //总数量
int count = 0; //单次数量
for (int flag = 0; flag < s.Length - 1; flag++)
{
if (s[flag] == s[flag + 1])
++count;
else if (s[flag] != s[flag + 1])
{
Console.WriteLine((char)s[flag] + ":" + count);
allCount += count;
count = 0;
}
if (flag == s.Length - 2)
{
Console.WriteLine((char)s[flag] + ":" + count);
}
}
Console.WriteLine("total:" + allCount);
}
}
}
时间复杂度比较
这两种算法的时间复杂度理论上将是一致的，因为比较的次数相等。
例如：array={a,a,a,b,b,c,c,c}
用第一种方法：
array[0] 和 array[1] array[2] array[3]比较，比较了三次
array[3] 和 array[4] array[5] 比较，比较了两次。
array[5] 和 array[6] array[7] 比较，比较了两次。
一共是7次。
用第二中方法:
array[0]和array[1] 比较。
array[1]和array[2] 比较。
array[2]和array[3] 比较。
...
也就等于array.Length-2,也就是7次。
在两个时间复杂度相等且代码实现上复杂度几乎一致（代码行数几乎相等）的情况下，我会选择第一种方法，因为在第二种方法中重复写了两次打印数量，有完全重复的代码，看起来不够优雅。😏
网友评论