算法-最长平台问题

算法-最长平台问题

清晨说ぺ晚安 发布于 2017-03-29 字数 186 浏览 1250 回复 3

(一些算法)
已知一个已经从小到大排序的数组,这个数组的一个平台就是连续的一串值相同的元素,并且这一串元素不能再延伸。求数组中最长的平台
例如 1,2,2,3,3,3,4,5,5,6

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

灵芸 2017-09-26 3 楼

这个问题其实主要是为了使用最少的比较次数来得到这个最长平台了,通常来说这个数组的重复数据比较多。
下面的代码当然还需要有很多的优化地方
当然肯定有其他的小bug,但基本想法如下

void findMaxLen(int *array, int len)
{
int i = 0;
int maxlen = 1;

int maxNum = 0;
int skip = 0;

for(i = 0; i < len; )
{
if(array[i] == array[i + max])
{
i = i + max;
if(skip == 1)
{
max *= 2;
}
else
{
max++;
skip = 1;
maxNum = array[i];
}

continue;
}

if((array[i] == array[i + 1]) && (array[i] == maxNum))
{
max++;
}
++i;
skip = 0;

}

printf("max = %dnnum = %dn", max, maxNum);
return max;
}

想挽留 2017-08-30 2 楼

给个php版:

<?php
$arr = array(1,1,2,2,2,3,3,4,4,4,4,5,5,5,6,6);
function long($arr) {
if (empty($arr))
{
return 0;
}
$length = 1;
$num = 0;
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] == $arr[$i - $length])
{
$num = $arr[$i];
$length++;
}
}
echo '数字为'.$num.'长度为'.$length;
}
long($arr);
?>

晚风撩人 2017-08-20 1 楼

..饿 线性扫描不就可以了- -.... 给一个n和num n表示开始的数的大小num表示当前n的个数。 最后n和num就是所谓的最长平台

if(array[i] == n)
++num;
else
{
n = array[i];
num=1;
}