算法笔记 03_众数问题


★问题描述:

    给定含有 n 个元素的多重集合 S,每个元素在 S 中出现的次数称为该元素的重数。多重集 S 中重数最大的元素称为众数。 
    例如,S={1,2,2,2,3,5}。多重集 S 的众数是 2,其重数为 3。

★编程任务:

    对于给定的由 n 个自然数组成的多重集 S,编程计算 S 的众数及其重数。

★算法思想——第一种:

① 当接收到 n 个数据,首先将其存入一个数组;
② 然后将这些数据进行从小到大的排序;
③ 要知道用户输入的数据即使排列好之后,相邻的数据也可能不是按照差值为 1 来递增的(可能为 2,4,4,7……)
   所以当出现相邻数据相等时,该如何来记录相同数据的个数呢。
   因此在这里要用地址的差值来计算,数据不会像 1,2,3…… 这样来排序,但地址是这样子
   所以只要设置两个指针来依次指向相邻数据的两个地址,当出现相同数据时,让前一个指针指向第一个重复的数据,
   将后一个指针指向最后一个重复数据的之后一个数据(参考:2~7 有几个数? 答:7-2+1)
   接着用后一个指针的地址,来减去第一个指针的地址,差值即为该重复数据的个数;
④ 用上一个步骤循环完所有数据后,将每一个重复数据的差值大小进行比较并保存,最后选择出最大的即可。
(注:令数组中最后一个有意义的数据为最大数 0*ffff,方便作为参考数,用以停止循环)

★C++ 代码如下(Visual Studio 2017 实现):

// 算法问题 2——1 众数问题(只写了整数的,浮点数同理,无非改改类型)
// 程序中我加了不少非必要的回车换行,意在使程序更清晰一些
// 注意:数组名 a = &a = &a[0]

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>    //标准库头文件
#include <algorithm>    //算法库头文件(各种函数)
#define Max 10      //宏定义一个 Max 为 10 ,在下面用于定义数组的大小,方便修改
#define Inf 0xffff  //宏定义一个最大数,65535

using namespace std;
int record[Max];    //定义一个存储输入数据的数组,大小设置为 10
int n;  //定义用户实际要输入的数据总数 n 
int mode, num_quantity;     //定义众数为 mode,定义众数的数量为 num_quantity

int main() {    //主函数

    printf("Please input the total number you like:\n");    
    scanf("%d", &n);   //读取用户要输入的数据总数 n

    printf("Please input the numbers:\n");    
    for (int i = 0;i < n;i ++)      
      scanf("%d", &record[i]);    //依次对用户输入的数据进行扫描,保存到 record 数组中

    sort(record, record + n);   //sort 函数作用:对给定区间所有元素进行升序排序

    record[n] = Inf;    //令数组最后一个有意义数据为最大值
    int *source = record, *target = record + 1;     //地址传值(指针指向地址): 定义 source 的值等于数组第一个数据(即最小值),
                                    //target 为数组接下来一个值,二者指的是地址大小
    
    num_quantity = 0;   //初始化众数的数量为 0

    while (*source != Inf) {    //条件为当 source 不等于最大值时
        while (*target == *source && *target != Inf)    //当 target 等于 source 并且 target 不等于最大值时
            target ++;      //target 地址大小 +1

        int temp = target - source;     //2个地址在计算,此时 target 已比source 大 2

        if (temp > num_quantity) {      //如果差值大于众数的数量
            num_quantity = temp;        //那么令众数的数量等于 temp
            mode = *source;     //众数即为此时 source 指向的值
        }

        source = target;    //令二者的地址相同
        target++;       //target 地址 +1 

    }    
    printf("The mode is: %d\n", mode);    
    printf("And its count is: %d\n", num_quantity);
    system("pause");    //暂停一下程序,显示输出
    return 0;
}


happysneaker.com


算法思想——第二种(见代码注释)

主要是运用了桶排序的部分思想

这里使用JAVA实现的,如下:

import java.util.Scanner;

public class zhongshuwentiiiiii {

	    zhongshuwentiiiiii(){
			int max=0,j=0,t,n;
			Scanner duqu = new Scanner(System.in); //先建立一个读取器再说

			System.out.println("请输入一共有几个元素:");
			n = duqu.nextInt();
			int[]xxx = new int[n];//初始化数组大小

			System.out.println("请输入数组中的每个元素:");
			for(int i=0;i<xxx.length;i++){ // 桶插入思想
				t=duqu.nextInt();
				xxx[t]++;
			}

			for(int i=0;i<xxx.length;i++){ // 求重复次数
				if(xxx[i]>=max) {j=i; max=xxx[i];}
			}
			System.out.println("众数为:"+ j);
			System.out.println("重复次数为:"+ max);
		}


	public static void main(String[] args){
		zhongshuwentiiiiii l1 = new zhongshuwentiiiiii();
	}
}

happysneaker.com

运行结果



Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论