统计一个只包含大写字母的字符串中顺序对的数量.其中顺序对的定义为前面的字符小后面的字符大.例如在“ABC“中的顺序对为3,因为有AB,AC,BC

admin管理员组

文章数量:1122850

统计一个只包含大写字母的字符串中顺序对的数量.其中顺序对的定义为前面的字符小后面的字符大.例如在“ABC“中的顺序对为3,因为有AB,AC,BC

哈希法：扫描字符串，将出现的字符次数加1，统计比当前字符字典序小的字母出现的次数，即为顺序串的个数。

int CounSq(const char* arr)//时间复杂度O（n）
{int sig[26] = { 0 };int index = 0;int sum = 0;for (int i = 0; arr[i] != '\0'; i++){index = arr[i] - 'A';sig[index]++;for (int j = 0; j < index; j++)//把前面比我小的字符全部加起来{sum += sig[j];}}return sum;
}int main()
{char arr[] = "ABC";int sum = CounSq(arr);printf("顺序对数量为：%d", sum);return 0;
}

二维数组处理

2.在一个只包含大写字母的3*3二维数组中统计符合顺序对的数量.统计包括每行(从左往右)也包括每列(从上往下)例如在如下的二维数组中：

int Councub(char arr[][3])
{int sum = 0;int sig[26] = { 0 };int index = 0;for (int i = 0; i < 3; i++)//横向顺序对{for (int j = 0; j < 3; j++){index = arr[i][j] - 'A';sig[index]++;for (int k = 0; k < index; k++){sum += sig[k];}}for (int n = 0; n < 26; n++)//每一行重新进行计算，将标志数组置空sig[n] = 0;}for (int i = 0; i < 3; i++)//竖向顺序对{for (int j = 0; j < 3; j++){index = arr[j][i] - 'A';sig[index]++;for (int k = 0; k < index; k++){sum += sig[k];}}for (int n = 0; n < 26; n++)sig[n] = 0;}return sum;
}int main()
{char arr[3][3] = { 'A','B','C','D','E','C','X','B','D'};int sum = Councub(arr);printf("数组中的顺序对为：%d", sum);return 0;
}

本文标签： 统计一个只包含大写字母的字符串中顺序对的数量其中顺序对的定义为前面的字符小后面的字符大例如在“ABC“中的顺序对为3因为有ABAcBC