挑战数据结构和算法面试题——最大间隔

题目来自伯乐在线,欢迎有不同答案的同学来一起讨论。

分析:

本题首先需要理解清楚最大间隔的最小:

  • 最初的间隔为:[1,1,4,1],此时最大间隔为4
  • 删除2后的间隔为:[2,4,1],此时最大间隔为4
  • 删除3后的间隔为:[1,5,1],此时最大间隔为5
  • 删除7后的间隔为:[1,1,5],此时最大间隔为5

在删除元素后的间隔为:[4,5,5],最小值为:4

方法:

int get_min_max_margin(int *a, const int n) {
  int *margin_array = (int *)malloc(sizeof(int)*(n-1));
  int max_ori = 0;
  int *p = margin_array;
  for (int i = 0; i < n-1; i++) {
    int margin = a[i+1] - a[i]; // 计算当前的间隔
    if (margin > max_ori) max_ori = margin;// 纪录所有最大的间隔
    *p = margin;
    p ++;
  }
  // 开始计算
  int *q1 = margin_array;
  int min_num = max_ori + max_ori;
  for (int j = 0; j < n-2; j++) {
    int max_num = max_ori;
    int *q2 = q1 + 1;
    int margin_new = *q1 + *q2;
    if (margin_new > max_num) max_num = margin_new;
    if (min_num > max_num) min_num = max_num;
    q1 ++;
  }
  free(margin_array);
  return min_num;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习AI算法工程

用python实现决策树ID3算法,对隐形眼镜类型预测

本节讲解如何预测患者需要佩戴的隐形眼镜类型。 1、使用决策树预测隐形眼镜类型的一般流程 (1)收集数据:提供的文本文件(数据来源于UCI数据库) (2)准备数据...

47670
来自专栏简书专栏

基于tensorflow+CNN的搜狐新闻文本分类

tensorflow是谷歌google的深度学习框架,tensor中文叫做张量,flow叫做流。 CNN是convolutional neural netwo...

35720
来自专栏人人都是极客

4.训练模型之准备训练数据

终于要开始训练识别熊猫的模型了, 第一步是准备好训练数据,这里有三件事情要做: 收集一定数量的熊猫图片。 将图片中的熊猫用矩形框标注出来。 将原始图片和标注文件...

52880
来自专栏GIS讲堂

postgis常用函数介绍(一)

在进行地理信息系统开发的过程中,常用的空间数据库有esri的sde,postgres的postgis以及mySQL的mysql gis等等,在本文,给大家介绍的...

40930
来自专栏liuchengxu

详解 MNIST 数据集

MNIST 数据集已经是一个被"嚼烂"了的数据集, 很多教程都会对它"下手", 几乎成为一个 "典范". 不过有些人可能对它还不是很了解, 下面来介绍一下.

30620
来自专栏机器之心

入门 | GPU是如何优化运行机器学习算法的?

422140
来自专栏智能算法

深度学习三人行(第2期)---- TensorFlow爱之再体验

上一期,我们一起学习了TensorFlow的基础知识,以及其在线性回归上的初体验,该期我们继续学习TensorFlow方面的相关知识。学习的路上,我们多多交流,...

376100
来自专栏ATYUN订阅号

Tensorflow 1.3.0版本的变更概述

尽管距离Tensoflow 1.2.1版本发布才仅仅一个月,但是1.3.0版本中的软件已经发生了很多变化。开发人员可以在Tensorflow的Github页面上...

38470
来自专栏本立2道生

Caffe源码理解1:Blob存储结构与设计

在逻辑上,Blob是个\(N_d\)维张量。当\(N_d=4\)时,Blob的shape定义为\(N * C * H * W\),即\(Num * Channe...

32020
来自专栏后端技术探索

一致性hash算法清晰详解!

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 ...

13420

扫码关注云+社区

领取腾讯云代金券