习题1.3 考虑由下列数所组成的表。你的工作是删去尽可能少的数使得留下来的数以升序排列。例如除了前两个数以外删去所有的数就会得到一个升序序列，删去除第1个、第3个、第6个、第8个数以外的其他数也将得到一个升序序列（可以比前面少删除一些数）。
9 44 32 12 7 42 34 92 35 37 41 8 20 27 83 64 61 28 39 93 29 17 13 14 55 21 66 72 23 73 99 1 2 88 77 3 65 83 84 62 5 11 74 68 76 78 67 75 39 70 22 71 24 25 26
大概估计了一下穷举法的时间跟空间复杂度。每个数字都有两个可能，选中或者选不中（某些情况下，一部分数字肯定是选不中的），可以据此建立一棵二叉树，节点是数字1（选中）或0（选不中），完成以后遍历二叉树，求出节点之和最大的所有路径。复杂度在2^N量级，一旦N达到几百几千，这是无法承受的。考虑过边构建二叉树边剪枝，没有标准，不可行。考虑过把连续的数字序列作为一个节点，优化空间有限。穷举法就这样被放弃了。
由于最终的结果是个升序序列，所以想到先给所有的数排序，然后映射并找出最长的升序序列。留下一个数的标准是什么？留下这个数的好处大于去掉这个数的好处。考虑过区间、向量、二维坐标图、先处理特殊数字，由于总想着找出最长的升序序列，而最长的升序序列是一个整体，一个数能不能最终留下来还跟其他数有关，都归于穷举法，所以都没解决问题。
这期间把未排序序列中的数字跟已排序序列中的同一个数字连线（容易联想起这条连线的区间），发现很多交叉线，需要通过删除一些数字来消除交叉，并且保证删除的数字个数最少，但是这个思路没有深入下去。后来回到这个思路，根据这张图又画了一张图，只有一组数字（数字分布在二维平面，不是之前的直线）；如果之前的图上两条连线有交叉，那就在新的图上给这两个数字连线。接下来需要删除最少的节点，让剩下的节点之间没有连线，解决方法：一直删除连线最多的节点，直到节点之间没有连线。（没有图不够直观，以后再补）
“找出最长的升序序列”就像给这个过程加了锁，可能等很久以后才能继续前进；“删除最捣蛋的数字”就像wait-free算法，在有限步之内就能继续前进。
下面是Java实现，试过1000个数字的序列，瞬间完成。为了让程序更清晰易懂，没有做优化。
Pre[-]
package algorithm.iaaa;
import java.util.*;
/**
* it'll try to find out an answer ASAP, but not to find out all the answers
*
* @author sandynz
*/
public class Ex1_3 {
public static void main(String[] args) {
Ex1_3 self = new Ex1_3();
Integer[] ints;
ints = new Integer[] { 91, 92, 93 };
self.printParamAndResult(ints);
ints = new Integer[] { 91, 92, 93, 94, 95, 8, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11 };
self.printParamAndResult(ints);
ints = new Integer[] { 91, 92, 93, 94, 95, 8, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
self.printParamAndResult(ints);
ints = new Integer[] { 9, 51, 54, 58, 7, 8, 61, 91, 62, 92, 93, 66, 96, 68, 98, 11, 12, 13, 14 };
self.printParamAndResult(ints);
ints = new Integer[] { 91, 92, 93, 8, 11, 12 };
self.printParamAndResult(ints);
ints = new Integer[] { 9, 44, 32, 12, 7, 42, 34, 92, 35, 37, 41, 8, 20, 27, 83, 64, 61, 28, 39,
93, 29, 17, 13, 14, 55, 21, 66, 72, 23, 73, 99, 1, 2, 88, 77, 3, 65, 83, 84, 62, 5, 11, 74,
68, 76, 78, 67, 75, 39, 70, 22, 71, 24, 25, 26 };
self.printParamAndResult(ints);
ints = new Integer[] { 91, 92, 93, 11, 12, 93 };
self.printParamAndResult(ints);
ints = self.getRandomInts(1, 2000, 1000);
self.printParamAndResult(ints);
}
Integer[] getRandomInts(int intStart, int intEnd, int len) {
Integer[] result = new Integer[len];
Random rnd = new Random();
for (int i = 0; i < len; i++) {
result[i] = rnd.nextInt(intEnd - intStart) + intStart;
}
return result;
}
public void printParamAndResult(Integer[] ints) {
System.out.println("=====================");
System.out.print(String.format("ints(len=%d): ", ints.length));
System.out.println(Arrays.asList(ints));
if (ints.length == 0)
return;
Integer[] result = makeIntegerArrayAscending(ints);
List<Integer> removedIntsIdxs = new ArrayList<>(), keptInts = new ArrayList<>();
for (int i = 0, len = result.length; i < len; i++) {
if (result[i] == null)
removedIntsIdxs.add(i + 1);
else
keptInts.add(result[i]);
}
System.out.print(String.format("removedIntsIdxs(len=%d): ", removedIntsIdxs.size()));
System.out.println(removedIntsIdxs);
System.out.print(String.format("keptInts(len=%d): ", keptInts.size()));
System.out.println(keptInts);
}
/**
* @return cloned ints, removed int element will be set as null
*/
public Integer[] makeIntegerArrayAscending(final Integer[] ints) {
final int intsLen = ints.length;
final Integer[] result = ints.clone();
final Integer[] idxsOfSortedIntsIdxs = getIdxsOfSortedIntsIdxs(ints);
// conflict counts
final int[] conflictCnts = new int[intsLen];
for (int i = 0; i < intsLen; i++) {
int idxi = idxsOfSortedIntsIdxs[i], idxj;
for (int j = 0; j < intsLen; j++) {
idxj = idxsOfSortedIntsIdxs[j];
if (j < i && idxj > idxi || j > i && idxj < idxi) {
conflictCnts[i]++;
}
}
}
// keep most ascending ints =>
// remove least int =>
// remove int which has the most conflict count, until no conflict
int maxConflictCnt, maxConflictIdx;
while (true) {
maxConflictIdx = 0;
maxConflictCnt = conflictCnts[0];
for (int i = 1; i < intsLen; i++) {
if (conflictCnts[i] > maxConflictCnt) {
maxConflictIdx = i;
maxConflictCnt = conflictCnts[i];
}
}
if (maxConflictCnt > 0) {
result[maxConflictIdx] = null;
conflictCnts[maxConflictIdx] = 0;
final int i = maxConflictIdx, idxi = idxsOfSortedIntsIdxs[i];
int idxj;
for (int j = 0; j < intsLen; j++) {
if (result[j] == null) {
continue;
}
idxj = idxsOfSortedIntsIdxs[j];
if (j < i && idxj > idxi || j > i && idxj < idxi) {
conflictCnts[j]--;
}
}
}
else {
break;
}
}
// remove duplicated ints
{
HashSet<Integer> intsSet = new HashSet<>();
for (int i = 0; i < intsLen; i++) {
if (intsSet.add(result[i]) == false)
result[i] = null;
}
}
return result;
}
private Integer[] getIdxsOfSortedIntsIdxs(final Integer[] ints) {
final Integer[] result = new Integer[ints.length];
Integer[] idxsOfSortedInts = new Integer[ints.length];
for (int i = 0, len = ints.length; i < len; i++) {
idxsOfSortedInts[i] = i;
}
Arrays.sort(idxsOfSortedInts, new Comparator<Integer>() {
@Override
public int compare(Integer idx1, Integer idx2) {
return ints[idx1] - ints[idx2];
}
});
for (int i = 0, len = idxsOfSortedInts.length; i < len; i++) {
result[idxsOfSortedInts[i]] = i;
}
return result;
}
}
=文章版本=
2013062320130624 增加重复数字删除；改改思路描述
No comments:
Post a Comment