import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Random;
public class Main {
for (int i = 0; i < array.length; i++)
array
[i
] = random.
nextInt(Integer.
MAX_VALUE);
long before
= System.
nanoTime(); LinkedList
<Integer
> linkedList
= new LinkedList
<Integer
>(Arrays.
asList(array
)); linkedList.add(-1);
ArrayList
<Integer
> arrayList
= new ArrayList
<Integer
>(Arrays.
asList(-1)); linearInsertion(array, arrayList);
System.
out.
println(arrayList.
equals(linkedList
)); }
private static void linearInsertion
(Integer[] intArray, ArrayList
<Integer
> list
) { for (int integer : intArray) {
for (int i = 0; i < list.size(); i++) {
if (integer > list.get(i)) {
list.add(i, integer);
break;
}
}
}
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuQXJyYXlzOwppbXBvcnQgamF2YS51dGlsLkNvbGxlY3Rpb25zOwppbXBvcnQgamF2YS51dGlsLkxpbmtlZExpc3Q7CmltcG9ydCBqYXZhLnV0aWwuUmFuZG9tOwoKcHVibGljIGNsYXNzIE1haW4gewoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBFeGNlcHRpb24gewoKICAgICAgICBJbnRlZ2VyW10gYXJyYXkgPSBuZXcgSW50ZWdlclsxMDAwMF07CiAgICAgICAgUmFuZG9tIHJhbmRvbSA9IG5ldyBSYW5kb20oKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhcnJheS5sZW5ndGg7IGkrKykKICAgICAgICAgICAgYXJyYXlbaV0gPSByYW5kb20ubmV4dEludChJbnRlZ2VyLk1BWF9WQUxVRSk7CgogICAgICAgIGxvbmcgYmVmb3JlID0gU3lzdGVtLm5hbm9UaW1lKCk7CiAgICAgICAgTGlua2VkTGlzdDxJbnRlZ2VyPiBsaW5rZWRMaXN0ID0gbmV3IExpbmtlZExpc3Q8SW50ZWdlcj4oQXJyYXlzLmFzTGlzdChhcnJheSkpOwogICAgICAgIGxpbmtlZExpc3QuYWRkKC0xKTsKICAgICAgICBDb2xsZWN0aW9ucy5zb3J0KGxpbmtlZExpc3QsIENvbGxlY3Rpb25zLnJldmVyc2VPcmRlcigpKTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oKFN5c3RlbS5uYW5vVGltZSgpIC0gYmVmb3JlKSAvIDEwMDApOwoKICAgICAgICBiZWZvcmUgPSBTeXN0ZW0ubmFub1RpbWUoKTsKICAgICAgICBBcnJheUxpc3Q8SW50ZWdlcj4gYXJyYXlMaXN0ID0gbmV3IEFycmF5TGlzdDxJbnRlZ2VyPihBcnJheXMuYXNMaXN0KC0xKSk7CiAgICAgICAgbGluZWFySW5zZXJ0aW9uKGFycmF5LCBhcnJheUxpc3QpOwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigoU3lzdGVtLm5hbm9UaW1lKCkgLSBiZWZvcmUpIC8gMTAwMCk7CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihhcnJheUxpc3QuZXF1YWxzKGxpbmtlZExpc3QpKTsKICAgIH0KCgogICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBsaW5lYXJJbnNlcnRpb24oSW50ZWdlcltdIGludEFycmF5LCBBcnJheUxpc3Q8SW50ZWdlcj4gbGlzdCkgewogICAgICAgIGZvciAoaW50IGludGVnZXIgOiBpbnRBcnJheSkgewogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGxpc3Quc2l6ZSgpOyBpKyspIHsKICAgICAgICAgICAgICAgIGlmIChpbnRlZ2VyID4gbGlzdC5nZXQoaSkpIHsKICAgICAgICAgICAgICAgICAgICBsaXN0LmFkZChpLCBpbnRlZ2VyKTsKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQo=