文档章节

基础算法----找出集合中最大和值的子数组,插入排序,找出数组中出现最多的元素

春哥大魔王的博客
 春哥大魔王的博客
发布于 2017/02/27 14:05
字数 356
阅读 31
收藏 0

玩法

给定数组,包含正负整数,找出对应和值最大的子数组;

解法

一个数只有加上大于0的正整数才会越来越大,否则遇到小于0的负整数重新计数;

实现

int[] arr = { 3, -6, 1, 2, 3, -1, 2, -5, 1, 2 };

#region 找出最大加值子数组
static string maxSubArr(int[] arr)
{
    int sum = 0;
    int start = 0;
    int end = 0;
    int temp = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        if (temp < 0)
        {
            start = i;
            temp = arr[i];
        }
        else
        {
           temp += arr[i];
        }
        if (sum < temp)
        {

            sum = temp;
            end = i;
        }
     }
    return start + "," + end;
}
#endregion

// start和end是子串头尾的两个坐标

输出

1,2,3,-1

找出数组的正左负右

给定数组包含正负整数,如何将正整数放左,负整数放右。可采用插入排序;

实现

static int[] arr3 = { 1, -2, -4, 5, 6, -3, -8, 6 };

static void leftOrRight2(int[] arr)
 {
    int start = 0;
    int end = arr.Length - 1;
    while (start != end)
    {
        while (start < end && arr[start] < 0)
        {
            start++;
        }
        while (start < end && arr[end] >= 0)
        {
            end--;
        }
        if (start < end)
        {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    }
}

找出数组中出现最多的元素

static int[] arr4 = { 0, 2, 2, 1, 2, 0, 2, 0 };

#region 找到数组中出现最多的元素
static void findMaxDisplay(int[] arr)
{
    int v = arr[0];
    int c = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        if (v == arr[i])
        {
           c++;
        }
        else
        {
            c--;
        }
        if (c == 0)
        {
            v = arr[i];
            c = 1;
         }
    }

    System.Console.WriteLine(v);
}
#endregion

源码

http://git.oschina.net/aspnet/Suan-Fa

© 著作权归作者所有

共有 人打赏支持
春哥大魔王的博客
粉丝 19
博文 149
码字总数 90189
作品 0
海淀
程序员
私信 提问
前端面试中的常见的算法问题

0. 前言 重要:如果文章内部有图片无法显示,请移步简书 查看。 今天在刷文章的时候,突然看到了一篇专门分享前端面试算法的文章。 趁着现在有时间,赶紧和大家分享一波。 下面直接开始正文。...

mr_lp
2016/12/23
0
0
海量数据面试题整理1.给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是

海量数据面试题整理   1. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?   方案1:可以估计每个文件安的大小为50G×64=320G,远远...

今幕明
2015/01/30
0
0
大数据处理面试题

给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 方an1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将...

zyt_1978
2016/04/14
130
0
海量数据处理 - 十道面试题与十个海量数据处理方法总结

第一部分、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 或者如下阐述(雪域之鹰):算法思想:分而治之+Hash1.IP地址最多有2^32=4G种取值情况,所以不能...

小王穷遊
09/02
0
0
海量数据处理:十道面试题与十个海量数据处理方法总结

1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射...

ahucsxl
2015/10/08
165
0

没有更多内容

加载失败,请刷新页面

加载更多

new Date() 在Safari下的 Invalid Date问题

问题复现 var timeStr = '2018-11-11 00:00:00';var time = new Date(timeStr);// error: Invalid Date... 在safari浏览器下,time为Invalid Date, 导致后面代码执行错误; 其他浏览器诸...

会写代码的husky
26分钟前
2
0
0009-如何升级Cloudera Manager和CDH

1.文档编写目的 本文档讲述如何升级Cloudera Manager和CDH,通过本文档,您将学习到以下知识: 1.如何对Cloudera Manager进行停机升级 2.如何对CDH进行停机升级 3.如何在不影响集群作业的情况...

Hadoop实操
36分钟前
1
0
vue2中引用 better-scroll的方法

文章主要介绍了vue2中引用better-scroll和使用 better-scroll的方法,使用时有三个要点及注意事项在文中给大家详细介绍 ,需要的朋友可以参考下 使用时有三个要点: 一:html部分 <div class...

前端攻城老湿
46分钟前
1
0
浅谈教你如何掌握Linux系统

linux能做什么?相信绝大数人都有这样的疑问。可以玩吃鸡吗?可以玩lol吗? 如果你是以娱乐的名义来评价linux的可用性,对不起,linux可能不适合你,因为linux是一个工具,他是教你聪明的,不...

linuxprobe16
53分钟前
1
0
java中线程池的生命周期

线程池生命周期包括: RUNNING:接收新的任务并处理队列中的任务 SHUTDOWN:不接收新的任务,但是处理队列中的任务 STOP:不接收新的任务,不处理队列中的任务,同时中断处理中的任务 TIDYING:所...

小刀爱编程
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部