408王道数据结构课后代码习题(六)

简介: 408王道数据结构课后代码习题(六)

2.2.3, 12


image.png


  • 找重复元素,且该元素个数要超过数组的一半,所以一个数组最多只有一个主元素
  • 暴力,就是拿空间换时间,类似桶排序
  • 开一个新数组,新数组的下标对应元素值,值对应元素个数(因为数的范围是确定的)
  • 时间复杂度O(n),空间复杂度O(n)


int find_main(SqList list) {
  // 1.初始化一个全为0的数组
  int tmp[list.length] = {0};
  // 2.新数组的下标对应元素值,值对应元素个数
  for (int i = 0; i < list.length; i++) {
    tmp[list.data[i]]++;
  }
  // 3.遍历找出主元素
  for (int i = 0; i < list.length; i++) {
    if (tmp[i] > list.length / 2 ) 
      return i;
  }
  // 4.没找到返回-1
  return -1;
}
复制代码


  • 第二种方法:我们先排好序再找主元素
  • 记录每个元素出现的次数,如果后面的数不是重复元素,就判断当前元素是否为主元素
  • 因为用了快排,时间复杂度O(nlog2n),空间复杂度O(logn)
  • 总分13分,这个解最高可以拿11分,所以不要强求最优解


int find_main2(SqList list) {
  // 1.快排
  sort(list.data, list.data+list.length);
  // 2.记录每个元素出现的次数,找到主元素
  int cnt = 1;
  for (int i = 0; i < list.length - 1; i++) {
    if (list.data[i+1] == list.data[i]) {
      cnt++;
    } else {
      if (cnt > list.length / 2)
        return list.data[i];
      cnt = 1;
    }
  }
  return -1;
}
复制代码


  • 这道题考试的时候(应该大概也许)可以不写跟题目无关的排序的具体实现
  • 因为快排每次递归需要的空间是固定的,递归层数即为空间复杂度,故快排的平均空间复杂度为O(log2n)
  • 快排的实现如下:


void quick_sort(int l, int r) {
  if (l == r) return; 
  int x = a[(l+r)/2];     // 1.枢纽元素
  // 2.分成两块
  int i = l-1, j= r+1;
  while (i < j) {
    while (a[++i] < x);   // 找到左边比x大的元素
    while (a[--j] > x);   // 找到右边比x小的元素
    if (i < j) swap(a[i], a[j]);  // 互换
  }
  // 3.递归
  quick_sort(l, j);
  quick_sort(j+1, r);
}
复制代码


  • 最优解,对对碰
  • 因为主元素个数要超过数组的一半,它就可以抵掉所有其他元素且有剩余
  • 时间复杂度O(n),空间复杂度O(1)


int find_main3(SqList list) {
  int c, cnt = 1;
  c = list.data[0];
  // 1.选定候选主元素
  for (int i = 1; i < list.length; i++) {
    if (list.data[i] == c) cnt++;
    else {
      if (cnt > 0) {
        cnt--;
      } else {
        c = list.data[i];
        cnt = 1;
      }
    }
  }
  // 2.统计实际数量
  if (cnt > 0) {
    cnt = 0;
    for (int i = 0; i < list.length; i++)
      if (list.data[i] == c) 
        cnt++;
  }
  // 3.确认主元素
  if (cnt > list.length / 2) return c;
  return -1;
}


目录
打赏
0
0
0
0
7
分享
相关文章
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
144 77
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
46 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】 目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果: 任务描述 本关任务:实现二叉排序树的基本算法。 相关知识 为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下: (1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。 (2)判断bt是否为一棵二叉排序树。 (3)采用递归方法查找关键字为6的结点,并输出其查找路径。 (4)分别删除bt中关键
54 11
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
63 15
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
49 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
47 10
|
1月前
|
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
45 10
|
1月前
|
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
50 10
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
39 7

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等