找出数组中的最值,去除重复元素

2014/05/2011:53:08 1

今天去面试,考官出了这样的一个题目,在下面的数组中找出数组的最值(最大值和最小值)

int array[10] = {2, 3, 1, 4, 9, 8, 5, 10, 7, 6};

当时我的想法是数组中每个元素肯定是要遍历的,因为要有最大值和最小值寻找,所以要有2n次的比较,当时就在想是不是要在如何比较两个的大小上面做优化(当时有点脑抽筋,想到以前见过的不用if,?:,switch来比较两个数的大小int array[2] = {a, b}, int max = array[a<b]),但是这里还是用到了比较,所有我那种方式还是不可取。

回来上网查了下,原来是要减少比较的次数,将原来数组中两个数比较最大值和最小值进行的4次比较减少为3次,这样比较次数就变为3n/2了,下面是算法实现

#include <stdio.h>

int main(int argc, char *argv[])
{
    int array[] = {2, 3, 1, 4, 9, 8, 5, 10, 7, 6};
    int len = sizeof(array) / sizeof(*array);
    int max = array[0];
    int min = array[0];
    int i, tmax, tmin, district;
    //判断数组长度的奇偶性
    if (len % 2 == 0)
    {
        district = len;
    } else 
    {
        district = len - 1;
    }
    //每次取出2个数进行3次比较,而不是每次取出1个数进行2次比较
    for(i=0; i<district; i+=2)
    {
        if (array[i] < array[i+1])
        {
            //记录两个数比较的结果
            tmax = array[i+1];
            tmin = array[i];
        } else 
        {
            tmax = array[i];
            tmin = array[i+1];
        }

        if (max < tmax)
        {
            max = tmax;
        }

        if (min > tmin)
        {
            min = tmin;
        }
    }
    //考虑到如果是奇数,最后一个数还有比较
    if (district == len - 1)
    {
        if (array[district] > max)
        {
           max = array[district];
        } 

        if (array[district] < min)
        {
            min = array[district];
        }
    }

    printf("max = %d, min = %d\n", max, min);
    return 0;
}

 

还有个题目是去除一个数组中的重复元素,列如下面的数组得到

array[10] = {2, 3, 1, 2, 1, 1, 4, 4, 5, 1};
//得到这样的结果
array = {2, 3, 1, 4, 5}

我在写的时候我用的是统计法,先找出数组中的最大数,然后用这个最大数来申请一个新的空间(时间复杂度是n)。考官说我的算法浪费空间,而且非整数不可用,这里我就不写我的实现了,写一个我回来写的实现

#include <stdio.h>
#include <malloc.h>

/* 表示数组这个数有重复存在 */
#define  EXIST 2147483647

int main(int argc, char *argv[])
{
    int array[] = {2, 3, 1, 2, 1, 1, 4, 4, 5, 1};
    int len = sizeof(array) / sizeof(*array);
    int i, j;

    for (i = 0; i < len; ++i)
    {
        for (j = i + 1; j < len; ++j)
        {
            /* 当数组后面的元素和前面元素有重复时 */
            if ( array[j] != EXIST && array[i] == array[j] )
            {
               array[j] = EXIST;
            }
        }
    }

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

    return 0;
}

 

  • 微信扫码赞助
  • weinxin
  • 支付宝赞助
  • weinxin

发表评论

您必须才能发表评论!

目前评论:1   其中:访客  0   博主  0   引用   1

    来自外部的引用: 1

    • julio