绝对值最小的元素and 数组中出现次数超过一半的元素

找出绝对值最小的元素

给定一个有序整数序列（非递减序），可能包含负数，找出其中绝对值最小的元素，比如给定序列 -5, -3, -1, 2, 8 则返回1。

分析

找出绝对值最小的元素：直接二分查找0该插入的位置，则要找的数就在插入位置本身，或者左边或右边。

#include
#include
#define N 15
int B[N];

int minabs(int B[],int n)
{
    int i=0;
    int min;
    if(n==1)
        return B[0];
    for(i=0;i
    {
        if(B[i]>0)
            break;
    }
    if(i==0)//所有都是正数
        min=B[0];
    else if(i==n)//所有都是负数
        min=B[n-1];
    else
        min=abs(B[i-1])
    return min;
}
int main()
{
    for(int i=0;i
    {
        scanf("%d",&B[i]);
    }
    int min=minabs(B,N);
     printf("the minabs of array %d\n",min);
    return 0;
}
/*
1 4 5 7 9 11 13 16 19 20 24 26 27 28 29
the minabs of array 1
Press any key to continue

-29 -28 -27 1 4 5 7 9 11 13 16 19 20 24 26
the minabs of array 1
Press any key to continue

*/

求数组中出现次数超过一半的元素

给定一个n个整型元素的数组a，其中有一个元素出现次数超过n / 2，求这个元素。据说是百度的一道题

分析

设置一个当前值和当前值的计数器，初始化当前值为数组首元素，计数器值为1，然后从第二个元素开始遍历整个数组，对于每个被遍历到的值a[i]

1 如果a[i]==currentValue，则计数器值加1

2 如果a[i] != currentValue， 则计数器值减1，如果计数器值小于0，则更新当前值为a[i]，并将计数器值重置为1

代码

// 找出数组中出现次数超过一半的元素
int Find(int* a, int n)
{
    int curValue = a[0] ;
    int count = 1 ;

    for (int i = 1; i < n; ++i)
    {
        if (a[i] == curValue)
            count++ ;
        else
        {
            count-- ;
            if (count < 0)
            {
                curValue = a[i] ;
                count = 1 ;
            }
        }
    }

    return curValue ;
}

另一个方法是先对数组排序，然后取中间元素即可，因为如果某个元素的个数超过一半，那么数组排序后该元素必定占据数组的中间位置