• 解题:乱序数组

    2016/12/04 Vinny Hu 22 评论

有一个乱序数组,例如:[3,1,4,8,2,10,6],请你删除最少的数字,使剩下的数字使递增的。

输出删除数字的个数。

样例如下:

输入:

输出:

【解题提示】:

  • 请在评论中先给出你的实现思路;
  • 然后贴出实现的代码;
  • 编程语言不限;
  • 评论支持代码高亮,请点击评论框菜单栏上的  < > 按钮;
  • 此题有两种复杂度的解法,一种是O(n^2)还有一种是O(nlog(n));

 

1 2 收藏


直接登录
最新评论
  • William   2016/12/05

    不就是求最长递增子序列吗。用二分查找时间复杂度就是nlogn了。

  • 瑜瑜100分 PHP工程师 2016/12/19

    一次循环就够了

  • c/c++

    int EraseCountOfNumbers(int a[],int n)
    {
    int max_len[n];
    int i = 1,j = 0,max_len_temp = 0,max_max_len = 0;
    for(i = 0; i < n; ++ i)
    {
    max_len[i] = 1;
    }

    max_max_len = max_len[0];
    for(i = 1; i < n; ++ i)
    {
    max_len_temp = max_len[0];
    for(j = 1; j < i; ++ j)
    {
    if(a[i] > a[j] && max_len[j] >= max_len_temp)
    {
    max_len_temp = max_len[j] + 1;
    }
    }
    max_len[i] = max_len_temp;
    if(max_max_len < max_len_temp)
    max_max_len = max_len_temp;
    }

    return n – max_max_len;
    }

  • 北极星   2016/12/26

    代码就不写了,使用冒泡算法;并累积交换次数。最终的交换次数即为删除数字的个数。

  • 失忆的金鱼 学生 01/12

    //刪除幾個數字是亂序數組變為有序數組
    public class shuzu {
    public void count(int []arr){
    int length = arr.length;
    int count = 0;
    for(int i = 1;i<length;i++){
    if(arr[i]<arr[i-1]){
    count++;

    }
    }
    System.out.println(count);
    }
    public static void main(String[]args){
    int arr[] = {3,1,4,8,2,10,6};
    shuzu shu = new shuzu();
    shu.count(arr);
    }
    }

  • 可可 程序员 01/17

    我用计数法算法复杂度是O(n^2)

    不知道作者的O(nlog(n))是什么思路

    • 可可 程序员 01/17

       

    • 可可 程序员 01/17

       

  • 小z   01/20

    输出3

  • 王念一 高一学生 02/13

    总感觉可以利用类似编辑距离的方法,打地图(虽然还是On^2

  • 风中2叔公   02/27

    假设数组a,x = a[0];

    for 遍历a数组

    if a[i] >= x 则 x=a[i]; ,否则 count++;

    最后输出count的值

    • 风中2叔公   02/27

      最后判断后面是否需要移下一数组元素,继续计算删除数的条件是a[0] 是否大于 a[1],是则以a[1]开始算一次,否则完了,看最大count输出就是了

  • 最少的数字是指数字的个数吗

  • 晓丹   03/01

    java 代码

     

  • hsu   03/02

     

  • ye_ibl .net 程序员 03/08

     

    using System;
    using System.Collections;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleApp1
    {
    class Program
    {
    static void Main(string[] args)
    {
    int[] num = { 7,1,2,3,5,8,6 };
    var min = num.Length;
    for (int i = 0; i < num.Length; i++)
    {
    var start = num[i];
    var deleteCount =i;
    for (int j = i+1; j < num.Length; j++)
    {

    if (num[j] < start)
    {
    deleteCount++;
    }
    start = num[j];
    }
    if (deleteCount < min)
    {
    min = deleteCount;
    }
    }
    Console.WriteLine(min);
    Console.ReadKey();

    }
    }
    }

  • tiptop∞   03/20

    试探:删除逆系数最大的数开始,然后删除次大的,直至数组有序

  • 日常写bug 软件工程师 03/22

    package Array;
    /*
    *
    */
    public class LuanxuArray {
    public static void main(String[] args) {
    int[] aa= {3,1,4,8,2,10,6};
    System.err.println(luanxu(aa)+”=====”+aa.length);
    }
    static int luanxu(int[] arr){
    int a = 0;//删除几个数
    int b =0;//递增序列长度
    int temp_num = 0; //递增序列长度对比数
    int temp = 0;//比较数字
    for (int i = 0;i < arr.length;i++){//以每一个数为首求最长递增序列
    if (i==0){
    temp = arr[i];
    } else {
    temp = arr[i];
    }

    for (int j = i ; j <arr.length;j++ ){//求得递增序列长度
    if (arr[j] > temp ) {
    temp =arr[j];
    temp_num++;
    System.err.println(i+”…”+temp_num);
    }
    }
    if (b == 0) { //求最长的递增序列
    b = temp_num;
    temp_num = 0;
    } else {
    if (b < temp_num ) {
    b = temp_num;
    temp_num = 0;
    }else {
    temp_num = 0;
    }
    }
    }
    a = arr.length – b -1;//求出删减数
    return a;
    }
    }