基础算法----找出集合中最大和值的子数组,插入排序,找出数组中出现最多的元素
基础算法----找出集合中最大和值的子数组,插入排序,找出数组中出现最多的元素
春哥大魔王 发表于10个月前
基础算法----找出集合中最大和值的子数组,插入排序,找出数组中出现最多的元素
  • 发表于 10个月前
  • 阅读 26
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

玩法

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

解法

> 一个数只有加上大于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

标签: 基础算法
共有 人打赏支持
粉丝 6
博文 46
码字总数 20422
×
春哥大魔王
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: