题目描述：已知碱基序列ACGT为正序。求任意碱基序列的逆序数。要求算法的时间复杂度为O(n)。
举例：一序列为AGTCTCG，则其逆序数为7。
#include <iostream> using namespace std; int reverse_order_number(char *pdna); int main() { char str[] = "ACTCTGA"; cout << reverse_order_number(str) << endl; return 0; } int reverse_order_number(char *pdna) { int sum = 0, i = 0; int c[4] = {0}; // 分别记录ACGT碱基的个数 while(pdna[i] != '\0') { switch(pdna[i]) { case 'A': // 如果当前元素是A，则将所有在A之前出现的C、G、T的个数和赋值给A，代表当前A的逆序数 sum = sum + c[1] + c[2] + c[3]; // c[0]++; //没什么用，A和后面的元素没有逆序数 break; case 'C': // 如果当前元素是C，则将所有在C之前出现的G、T的个数和赋值给C，代表当前C的逆序数 sum = sum + c[2] + c[3]; c[1]++; // 统计字符C出现的次数 break; case 'G': // 如果当前元素是G，则将所有在G之前出现的T的个数和赋值给G，代表当前G的逆序数 sum = sum + c[3]; c[2]++; // 统计字符G出现的次数 break; case 'T': // 因为T之前的没有比T大的逆序字符，所以不需要计算sum c[3]++; // 统计字符T出现的次数 break; } i++; } return sum; }
