Chinaunix首页 | 论坛 | 博客
  • 博客访问: 426691
  • 博文数量: 103
  • 博客积分: 5010
  • 博客等级: 大校
  • 技术积分: 971
  • 用 户 组: 普通用户
  • 注册时间: 2007-06-11 17:22
文章分类
文章存档

2008年(77)

2007年(26)

我的朋友

分类: C/C++

2008-03-17 19:24:13

算逆序数可以在O(n)时间内完成:

int count_inver(char *str, int len)
{
        int i;
        int cnt = 0;
        int a[4] = {0};
        for(i = len - 1; i >= 0; i--) {
                switch (str[i]) {
                        case 'A':
                                a[1]++;
                                a[2]++;
                                a[3]++;
                                break;
                        case 'C':
                                a[2]++;
                                a[3]++;
                                cnt += a[1];
                                break;
                        case 'G':
                                a[3]++;
                                cnt += a[2];
                                break;
                        case 'T':
                                cnt += a[3];
                }
        }
        return cnt;
}

阅读(671) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~