那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

在一个有序序列中查找重复/不存在的数

首先说明一下这个问题中提到的"有序序列"的概念.它指的是其中的元素在序列长度范围之内,而且是有序(比如升序)排列的序列.比如一个只包含10个元素的数组, 其中的元素大小在[0, 9]之间,而且是升序排列的.

这两个问题是二分查找算法的典型应用.

首先来看看查找不存在元素的算法.假设一个元素x不存在, 那么在序列中, 在x位置的元素是x + 1, 以此类推.

初始化 left = 0, right = len - 1 (其中len是这个有序序列的长度, 假设序列从0开始)

当left 
<= right时继续循环:
      pos 
= (left + right) / 2
     
      如果 序列的第pos个元素不等于pos
              那么不存在的元素一定出现在pos之前, 将right 
= pos - 1
      否则
              pos之前的元素都是存在的, 因此 left 
= pos + 1

根据上面的查找原则, 在left之前的元素都是存在的, 返回left

再来看看查找重复元素的算法.假设一个元素x重复出现, 那么在序列中, 在x + 1位置的元素是x, 而x+1出现在序列的x+2位置上, 以此类推.
从上面的算法可以看出, 最后返回的位置, 在它之前的元素位置都是正确的, 就是说,出现在了它们应该出现的位置, 因此, 上面算法也依然可以用于这个问题上面, 只要把上面算法的返回值 - 1即可以得到本算法要求的返回值.

关于这个问题,我之前有过类似问题的讨论:
1) 二分查找算法(迭代和递归版本)
2) 求出不在里面的数来
这个问题的讨论也是对<<编程珠玑>>第二章第一个算法问题的补充.

C代码如下:
/*
 * 查找有序序列中 重复/不存在 的数算法演示
 * 版权所有:
http://www.cppblog.com/converse/
 
*/

#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<time.h>

#define FUNC_IN()   printf("\nin  %s\n\n", __FUNCTION__)
#define FUNC_OUT()  printf("\nout %s\n\n", __FUNCTION__)

/* 生成一个长度为len的数组, 其中array[i] = i(0<=i<len) */
void generate_array(int array[], int len);
    
/* 向长度为len的有序数组中新增一个元素x(0<=x<len - 1), 同时保持原有数组有序 */
void add_to_array(int array[], int len, int x);

/* 删除长度为len的有序数组中的一个元素x(0<=x<len), 同时保存原有数组有序 */
void del_from_array(int array[], int len, int x);

/* 打印一个数组 */
void display_array(int array[], int len);

/* 查找一个长度为len的有序数组中哪个元素不存在 */
int find_not_exist(int array[], int len);

/* 查找一个长度为len的有序数组中哪个元素重复了 */
int find_duplicate(int array[], int len);

int main(int argc, char *argv[])
{
    
int count = 10;
    
int *array = NULL;

    srand(time(NULL));

    
if (argc == 2)
    {
        count 
= atoi(argv[1]);
    }

    
/* 申请内存的时候多申请一个元素 */
    
if ((array = (int *)malloc((count + 1* sizeof(int))) == NULL)
    {
        printf(
"malloc error!\n");
        exit(
-1);
    }

    
/* 首先生成一个元素都是有序的整型数组 */
    generate_array(array, count);

    display_array(array, count);

    
/* 删除其中的一个元素 */
    del_from_array(array, count, rand() 
% count);

    display_array(array, count);

    
/* 查找不存在的元素 */
    
int x = find_not_exist(array, count);
    printf(
"the element not exist is %d\n", x);

    
/* 把删除的元素补上 */
    add_to_array(array, count 
+ 1, x);

    
/* 新增一个重复的元素 */
    add_to_array(array, count 
+ 1, rand() % count);

    display_array(array, count 
+ 1);

    
/* 查找重复的元素 */
    printf(
"the element duplicate is %d\n", find_duplicate(array, count + 1));

    free(array);

    
return 0;
}

void generate_array(int array[], int len)
{
    
int i;

    
for (i = 0; i < len; ++i)
    {
        array[i] 
= i;
    }
}

void add_to_array(int array[], int len, int x)
{
    
int i;

    
/* 把[x + 1, len - 1]之间的元素右移一个位置 */
    
for (i = x + 1; i < len - 1++i)
    {
        array[i 
+ 1= i;
    }

    
/* x + 1的位置保存重复的x, 这样数组仍然是有序的 */
    array[x 
+ 1= x;
}

void del_from_array(int array[], int len, int x)
{
    
int i;

    
/* 将[x, len)的元素向左移动一个位置 */
    
for (i = x; i < len; ++i)
    {
        array[i] 
= i + 1;
    }

    printf(
"del_from_array element is %d\n", x);
}

void display_array(int array[], int len)
{
    
int i;

    printf(
"\n{ ");
    
for (i = 0; i < len; ++i)
    {
        printf(
"%d ", array[i]);
    }

    printf(
"}\n");
}

int find_not_exist(int array[], int len)
{
    FUNC_IN();

    
int left, right, pos, count;

    
for (left = 0, right = len - 1, count = 1; left <= right; count++)
    {
        pos 
= (left + right) / 2;

        printf(
"[%d] left = %d, pos = %d, right = %d\n", count, left, pos, right);

        
/*
         * 如果array[pos] != pos, 那么不存在的元素一定在[left, pos - 1]之间
         
*/
        
if (array[pos] != pos)
        {
            right 
= pos - 1;
        }
        
else
        {
            left 
= pos + 1;
        }
    }

    FUNC_OUT();

    
/* left之前的元素都是存在的 */
    
return left;
}

int find_duplicate(int array[], int len)
{
    
/*
     * find_not_exist()函数的返回值表示在它之前的元素都是正确的, 
     * 因此这个返回位置就是有重复的元素位置 + 1, 于是要减去1
     * 
*/
    
return find_not_exist(array, len) - 1;
}





posted on 2009-08-23 20:24 那谁 阅读(4532) 评论(3)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 在一个有序序列中查找重复/不存在的数  回复  更多评论   

为什么不用BitArray?
遍历一次就搞定!
2009-08-24 12:20 | 阿福

# re: 在一个有序序列中查找重复/不存在的数  回复  更多评论   

@阿福
别人是搞算法的...
用容器只是应用
2009-08-24 16:09 | Norz

# re: 在一个有序序列中查找重复/不存在的数  回复  更多评论   

@阿福
你可能没有仔细看我对问题的描述,事实上,如果使用这里所用的二分查找算法,都不用遍历一次,O(log(n))的时间复杂度就搞定问题了.
2009-08-24 16:23 | 那谁

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理