列表操作算法太慢

-2

有n个整数a1，a2，...，an的序列。我们需要用最小的元素来改变序列中的每个元素，它们放在它之前。如果没有这样的元素，我们需要用-1代替它。所有的变化都是同步的和独立的。列表操作算法太慢

例子：

4 3 1 2 1 - > -1 4 3 3 2

5 4 3 2 1 - > -1 5 4 3 2

我的代码是太慢和序列太大时，不会通过测试，并显示超时错误。我怎样才能提高其表现？

这里是我的代码：

public static void main(String[] args) throws InterruptedException { 
    ArrayList<Integer> list = new ArrayList<>(); 
    Scanner scanner = new Scanner(System.in); 
    int nElements = scanner.nextInt(); 
    for (int i = 0; i < nElements; i++) { 
     list.add(scanner.nextInt()); 
    } 
    ArrayList<Integer> newList = new ArrayList<>(); 
    for (int i = 0; i < list.size(); i++) { 
     int tmp = -1; 
     for (int j = i - 1; j >= 0; j--) { 
      if (list.get(i) < list.get(j)) { 
       if (list.get(j) < tmp || tmp == -1) { 
        tmp = list.get(j); 
       } 
      } 
     } 
     newList.add(tmp); 
    } 
    list = newList; 
}

更新：我忘了提，新的价值应该比我们改变元素更大。

来源

2017-10-07 bengan

究竟是什么要求？我没有得到这些例子。请注意，您可以通过对最终大小进行良好估计来加速ArrayList。你在构造函数中将它作为'initialCapacity'来告诉它。 – Zabuza

不应该是'4 3 1 2 1 - > -1 4 3 1 1'？ – janos

你不应该需要内部循环。元素i之前的最小元素是（元素i-1之前的最小值）和（元素i-1）的最小值。你只需一次就可以完成。 –

感谢cpp初学者的建议！树集和天花板的方法使它的工作：

public static void main(String[] args) throws InterruptedException { 
    ArrayList<Integer> list = new ArrayList<>(); 
    Scanner scanner = new Scanner(System.in); 
    int nElements = scanner.nextInt(); 
    for (int i = 0; i < nElements; i++) { 
     list.add(scanner.nextInt()); 
    } 
    ArrayList<Integer> newList = new ArrayList<>(); 
    TreeSet<Integer> set = new TreeSet<>(); 
    for (Integer aList : list) { 
     Integer tmp = set.ceiling(aList + 1); 
     if (tmp == null) { 
      newList.add(-1); 
     } else { 
      newList.add(tmp); 
     } 
     set.add(aList); 
    } 
    list = newList; 
}

谢谢大家！

来源

2017-10-07 14:09:45 bengan

public static void main(String[] args) { 
    int[] values = {10,3,5,7,9,2,2,14,-5,7,9,3}; 

    if (values.length == 0) { return; } 

    int minValue = values[0]; 
    int temp; 
    values[0] = -1; 

    for(int i=1; i<values.length; i++) { 
     temp = values[i]; 
     values[i] = minValue; 
     if (temp < minValue) { 
      minValue = temp; 
     } 
    } 

}

您可以记住直到当前项目的最小值，并在找到新项目时将其替换。这个运行在O（N）中，不需要额外的内存。

来源

2017-10-07 12:42:27

我认为你的代码会一直写-1直到找到一个更小的值（另外，如果前面的条件为false，请注意'int minValue'行失败）。 –

谢谢@AndyTurner，我编辑了我印刷数字的原始版本，并没有检查它，我的坏，现在应该工作:) –

由于嵌套循环的构造方式，您的方法当前是O（n^2），其中n是列表的大小。

您不需要内部循环：您已经有一个上一个要添加到列表中的值，即新列表中的上一个值。如果输入列表中相应的前一个元素较小，则下一个元素只会更小。所以就拿这两个数字中较小的那个。

List<Integer> newList = new ArrayList<>(); 
if (list.size() > 0) { newList.add(-1); } 
if (list.size() > 1) { newList.add(list.get(0)); } 
for (int i = 2; i < list.size(); i++) { 
    newList.add(Math.min(list.get(i-1), newList.get(i-1))); 
}

来源

2017-10-07 12:46:16

我忘了提及新值应该大于我们改变的元素。所以2不能改为1，只有3。 – bengan

列表操作算法太慢

回答

相关问题