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

顺序对的数量.其中顺序对的定义为前面的字符小后面的字符大.例如在“ABC“中的顺序对为3,因为有AB,AC,BC"/>

统计一个只包含大写字母的字符串中顺序对的数量.其中顺序对的定义为前面的字符小后面的字符大.例如在“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;
}