精华内容
下载资源
问答
  • 无序数组的中位数(c语言版本)

    千次阅读 2019-03-22 16:06:41
    在面试时,会经常被问道,如何求解一个无序数组的中位数?很多人往往都会第一感觉就是,先将该数组排序,然后找出最中间的那个数,但是这种思路通常的时间复杂度最好是O(nlogn),更糟的情况下会到O(n^2),并不是最优...

    在面试时,会经常被问道,如何求解一个无序数组的中位数?很多人往往都会第一感觉就是,先将该数组排序,然后找出最中间的那个数,但是这种思路通常的时间复杂度最好是O(nlogn),更糟的情况下会到O(n^2),并不是最优解,也就不能impressed面试官了。下面我们聊聊这个话题。

    何为中位数?

    中位数,就是数组排序后位于数组最中间位置的那个元素。当然,细分析的话,还要区分该数组的长度,如果该数组长度为n,若n为奇数,则中位数就是(n+1)/2位置上的数;若n为偶数,则中位数是n/2和n/2+1位置上的两个数的平均值,这里我们为了简单起见,就用n/2位置上的数代替吧。

    现在我们考虑一个更一般的问题:

    如何求解一个无序数组的第k小的数?

    如果能求解出第k小的数,那么就能求出第k大的数(它对应第(n-k)+1小的数),特别地,如果k为n/2或(n+1)/2的话,这就是我们要求的中位数。

    关于这个问题,我发现在Allen Weiss的《数据结构与算法分析》一书中一直贯穿始终,特别是在第七章排序中,给出了时间复杂度为O(n)的解决方法,该解决方法,也就是一个"二分法"思想的快速排序思想的变体,但是比快速排序的实现更快更简单,因为它只需要对牵涉范围的那些子数组排序。

    下面是我的源码实现,以作备忘。

    //description: 查找无序数组中指定的第k小的数
    //date: 2019-03-21
    
    #include <stdio.h>
    #include <stdlib.h>
    
    void swap(int arr[], int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
    
    void quick_select(int arr[], int k, int s, int e){
        if(s > e || k < s || k > e){
            printf("invalid array range\n");
            return;
        }
    
        //这里随机将左边第一个元素设置为基准点
        int i, j, pivot = arr[s];
        if(s <= e){
            i = s;
            j = e;
            for(;;){
                while(arr[j] >= pivot && i<j){j--;}
                while(arr[i] <= pivot && i<j){i++;}
                if(i<j)
                    swap(arr, i, j);
                else
                    break;
            }
            //恢复pivot
            swap(arr, i, s);
    
            //继续进行下一轮迭代
            if(k<=i)
                quick_select(arr, k, s, i-1);
            else if(k>=i+1)
                quick_select(arr, k, i+1, e);
        }
    }
    
    //数组复制
    void copy_array(int arr[], const int barr[], int n){
        int i = 0;
        for(i=0; i<n; i++)
            arr[i] = barr[i];
    }
    
    int main(int argc, char** argv){
        int a[] = {12,4,3,67,900,22,28,9,61,53,23,12};
        int n = sizeof(a) / sizeof(int);
        int k = 4;
    
        int b[n];
        copy_array(b, a, n);
        int m = n%2==0 ? n/2 : (n+1)/2;
    
        //求第k小的数
        quick_select(a, k, 0, n-1);
        printf("the %d-th smallest number: %d\n", k, a[k-1]);
    
        for(int i=0; i<n; i++)
            printf("%d ", a[i]);
        printf("\n");
    
        //求解中位数
        quick_select(b, m, 0, n-1);
        printf("the median nuber(%d-th): %d\n", m, b[m-1]);
    
        for(int i=0; i<n; i++)
            printf("%d ", b[i]);
        printf("\n");
    
        return 0;
    }

    这里给出了求解第4小和第6小的数的排序,因为数组长度为12,我就把6当做是该数组的中位数了。

    运行截图如下:

     

    展开全文
  • C语言的二维数组

    2018-04-17 13:18:25
    1.在定义数组的一个函数sizeof 2.在定义数组的一个函数,&amp;arr+1 其他情况下表示数组首地址 二、二维数组 那既然一维数组数组名在一般情况下表示数组首地址,那二位数组数组名是不是也代表...

    一、一维数组

    一维数组数组名在下面两种情况表示整个数组:

    1.在定义数组的同一个函数中,求sizeof

    2.在定义数组的同一个函数中,&arr+1

    其他情况下表示数组首地址

    二、二维数组

    那既然一维数组数组名在一般情况下表示数组首地址,那二位数组数组名是不是也代表数组首地址?

    二维数组本质上是以数组作为数组元素的数组,即“数组的数组”

    由下面的源代码可以看出

    #include <stdio.h>
     
    int main() 
    {
        int array[3][5] = {0};//定义一个二维数组(3行5列)
        int temp = 0;//设定一个临时的整型变量,用来给数组赋值
        for (int a = 0 ; a < 3; a++)//外层循环给数组的第一维赋值,就是array[x][y]的x
        {
            for (int b = 0 ; b < 5; b++)//内层循环给数组的第二维赋值,就是array[x][y]的y
            {
                temp = temp + 1;//为了让数组的数值不同,让临时变量有自增
                array[a][b] = temp;//二维数组的真正数据
                printf("array[%d][%d] = %-4d",a,b,array[a][b]);//打印出数组
            }
             printf("\n");//输出一行后换行
        }
        return 0;
    }

    输出为:

     

    那二维数组可以和一维数组一样,像一维数组一样给函数传递数组名首地址吗?

    答案是不能,因为一维数组只是数组,二维数组是数组的数组。

    我们从下面可以看到

    我们从左至右,从上至下讨论,

    arr此时是一维数组数组名,即代表数组的首地址,也即是指针,变量类型int *

    arr+1此时使用指针加法(可以看我指针的使用),变量类型int *

    arr[0]此时为int型数据

    brr此时是二维数组的数组名,即是数组的数组的首地址,也即是数组的指针,变量类型为int (*p)[4]

    (brr是三个(长度为四的数组)的数组,所以类型为int (*p)[4],如果长度为五,则是int (*p)[5]

    brr+1此时使用指针加法,变量类型int (*p)[4]

    brr[0]此时可理解为一位数组的数组名,变量类型为int *

    brr[0]+1此时使用指针加法,变量类型为int *

    brr[0][0]此时为int型数据

    三、注意区分数组指针与指针数组

    数组的指针:指向数组(不是数组首地址)的指针

    int (*p)[4]

    指针的数组:存放指针的数组

    int *p[4]

    展开全文
  • 求一个有序数组中两个元素值相加为k数字,返回这两个元素下标。要求时间复杂度O(n),空间复杂度为O(1) 思路: 因为是有序数组,所有将数组中前一部分元素和后一部分元素相加,这样循环最终得到最终我们想要...

    题目:
    求一个有序数组中两个元素值相加为k的数字,返回这两个元素的下标。要求时间复杂度位O(n),空间复杂度为O(1)
    思路:
    因为是有序数组,所有将数组中前一部分的元素和后一部分的元素相加,这样循环最终得到最终我们想要的答案

    源码:

    在这里插入图片描述

    运行结果如下:

    在这里插入图片描述

    展开全文
  • 4.寻找两个正序数组的中位数 我的代码(c语言版) 我的想法是先用一个新的数组把两个数组合并,再对新数组排序(此处用的是冒泡排序),最后根据新数组长度是奇数还是偶数中位数 double findMedianSortedArrays...

    4.寻找两个正序数组的中位数
    在这里插入图片描述
    在这里插入图片描述
    我的代码(c语言版)
    我的想法是先用一个新的数组把两个数组合并,再对新数组排序(此处用的是冒泡排序),最后根据新数组长度是奇数还是偶数求中位数

    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
        int new[2000];
        int len1,len2,len3,i,j,t;
        len1=sizeof(nums1);
        len2=sizeof(nums2);
        len3=len1+len2;
        for(i=0;i<len1;i++){
         new[i]=nums1[i];
     }
     for(i=len1;i<len3;i++){
      new[i]=nums2[i];
     }
     for(j=0;j<len3-1;j++){
      for(i=0;i<len3-1-j;i++){
       if(new[i]>new[i+1]){
          t=new[i];
          new[i]=new[i+1];
          new[i+1]=t;
       }
      }
     }
     if(len3%2==0){
      return (new[len3/2]+new[len3/2+1])/2;
     }
     else{
      return new[(len3+1)/2];
     }
    }

    运行了一下显示执行错误,后来看评论里说有要求,要把时间复杂度限制在O(log (m+n)),看了评论说是要用二分查找,等我再深入研究一下二分查找再来做这道题

    展开全文
  • 二、输入10个整数(通过指针引用数组),实现三个函数,分别这10个整数平均值、中位数、中值(数组名作为函数参数、通过指针引用数组),最后实现一个求平均值、中位数、中值通用函数(指向函数指针),要求...
  • C语言——二分法查找一个数_数组

    千次阅读 2020-03-31 18:03:03
    C语言——二分法查找一个数_数组 问题描述: 针对一个按顺序排列一维数组,用户输入一个数,如何辨别它是否存在?是数组中的第几? 编程思想: 采用二分法,以最中间的数和用户输入的数进行比较,逐步缩小所求数...
  • 先来个简单样例 int a[] = {1,2,3}; int arr_len = 0;...arr_len = sizeof(a)/sizeof(int);...解释:sizeof() keyword是出对象所占用内存...一个整数在32系统上占用4个字节,不同系统数值可能不同, 用siz...
  • #include int main(int argc, const char * argv[]) { int i,num;...在xcode上编译,利用breakpoint查看,无论怎么输入数组a中的a[0]都是0, 实在不知道问题出在哪里,请各位帮忙看看,谢谢啦
  • 1、先来例子,计算a*b=c,理解数组中的每位数逐个相乘步骤: 987*654;利用数组计算,则a[0]=9,a[1]=8,a[2]=7;b[0]=6,b[1]=5,b[2]=4; 第趟计算,用9分别与6、5、4相乘,得:c[0+0]=54,c[0+1]=45,c[0+2]=36;...
  • 这个程序是肯定有问题的...第一次循环最后i指向数组的最后一位数,之后执行i++,那么i指向了哪里?j的值又变成了什么? 为什么最后显示出来的结果只是数组的一个数和最后一个数相同其他的都没有变化? 大神解答...
  • 1.分别十百数字 #include<stdio.h> int main() { int a=456,x,y,z; x=a/100; y=a/10-10*x; //比较难理解 a/10就为非位数 //非位数为45,45减去最高位的10倍就是该 z=a%10; print...
  • - 我想分两步走,第步算出几数字没问题, 第二部通过取余数分别取出十百千数字 - 取余数失败, position数组中所有赋值都是零 - 我看了晚上也没研究明白, 大神指点, 感激不尽 ```c #include ...
  • 满意答案muwen37982014.01.04采纳率...问题是:-如果你想保留这个,那么用一个字符串数组来存储每一数字是可以。-你想计算是否能被3整除,那么你可以利用一个数学定理来完成这个计算,无需大内存,只要一小...
  • 初学C语言2.1-数组

    2019-11-27 09:11:05
    数组的定义 类型 数组名[元素个] ...// 访问a数组的第一个元素 循环跟数组的关系 例:尝试用数组存放十同学的数学成绩,并平均值 #include <stdio.h> #define NUM 10 //定义宏命令 int mai...
  • 斐波拉契数是指一个数组中从第三个起,一个数等于他前两位数的和,由这样有序数列叫斐波拉契数列。例如 //1 2 3 5 8 13 21 34 55 89 这就是1-10斐波拉契数。 而在算法如何求得斐波拉契数需要知道最基本定义...
  • 编写程序n!--C语言中数组的使用

    千次阅读 2013-03-30 22:41:18
    分析:数字相乘可以分解为各个阶相乘,比如百位数A*B可分解为A100*B+A10*B+A1*B,然后从小到大分析,如果某一位的值大于等于10,则需要向高位进位,并对该除以10,余数为该位的值。比如24*5,等价于(2*5)*...
  • 本题要求实现一个函数,N个集合元素A[]的中位数,即序列中第⌊N/2+1⌋大的元素。其中集合元素的类型为自定义的ElementType。 函数接口定义: ElementType Median( ElementType A[], int N ); 其中给定集合...
  • (4)将排序后的数组a组成一个值为最小整数(记为min); (5)输出min及其位数(两中间以空格分隔)。 麻烦列位大神看看哪里错了,输出不出值 #include #include int main(void){ int x,j,i,sum,t,d,...
  • C语言求相同数字

    2021-01-11 12:30:35
    求一个整数中的相同数字,如输入123456321,输出 1 2 3. 思路:首先求出输入整数位数,然后设置两个数组。a数组存放整数各个数字,b数组存放各个数字出现次数。 由于int类型数字长度限制,输入数字太大如...
  • C语言求水仙花

    2021-04-03 12:57:30
    问题描述: 将1000以内水仙花数存放到数组中(水仙花数指一个位数的各位数字立方和等于该数字值) 算法分析:利用for循环遍历100-1000内数,再判断该数符不符合水仙花数条件,并存入数组,利用三个...
  • 思想:将矩阵看做一个二维数组,用scanf()函数输入矩阵,将数组设置为最大值max,将max与数组中数按顺序两两比较,更新max,比较到最后一得到最终max。void main(){ int a[3][4],i,j,max,max_i,max_j; printf...
  • n个数据中的中间大小1个或2个。 可以建两个大小都是n / 2堆。第一个堆是小顶堆,第二个堆是大顶堆。要求大顶堆堆顶元素 < 小顶堆堆顶元素,如果不符合,就交换两个堆堆顶元素,维护这两个堆。最后...
  • C语言数组之排序

    千次阅读 2019-03-25 19:56:34
    基本过程是先将第一个数分别于后面的数一个一个进行比较,若后面的数小,则交换后面这个和第一个数的位置,否则不交换,一轮比较结束后就出了一个最小值的数放在了第一。然后进入第二轮比较,即在其余的数中再...
  • 本题要求实现一个函数,N个集合元素A[]的中位数,即序列中第⌊(N+1)/2⌋大的元素。其中集合元素的类型为自定义的ElementType。 函数接口定义: ElementType Median( ElementType A[], int N ); 其中给定集合元素...
  • C语言 数组练习题

    万次阅读 多人点赞 2018-07-24 16:25:38
    运算符是对字节或字中的实际二进制操作,只能操作二进制 ...1.有n个人围成一圈,顺序排号,从第一个开始报(从1到3报),凡报到3人退出圈子,问最后留下是原来第几号. #include <stdio.h...
  • //从键盘输入一个数字(可以包含小数点,其位数在60以下,其整数有效位数,如输入 //0123.456,返回值为整数有效位数为3) //1) 输入数据为浮点型,不用数组,不用字符串,只有变量算术运算实现此功能。
  • 指教:cxdsz[p+1]是 int 类型数组中的一个数值,怎样出这个数值位数,或者说就是想在LCD1602上显示出这个? char array[]="cxdsz[p+1]" ; len=strlen( array ) ; for(q=0;q;q++) LcdWriteData...
  • 编写一个通用函数该函数可以实现判断一个含有五数字整数是否是回文回文数的含义是从左向右与从右向左看是相同如23732是回文而23564则不是编写主程序调用该函数实现所有5数字满足条件的数的个数 #...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 201
精华内容 80
关键字:

c语言求一个数组的中位数

c语言 订阅