面试题求解，高手请入

0 0

面试题求解，高手请入5

求一个一维数组的递增子序列个数，比如[2,3,1,4]，有 [2,3],[3,4],[1,4],[2,3,4]四个，函数返回值为4；
时间复杂度，N*logN

2014年9月04日 16:23

wsgjj
20
0 0 2

这道算法题应该不难，其实他应该就是考虑组合问题，我们其实可以这样分析：
对于一个递增组合来说，后一个值必须要大于前一个值，无论这个组合有多大都必须要满足这样一个条件，那么对于组合[1，2，3，4]来说，对于节点1来说，满足包含1的所有全排列为C(3，1)+C(3，2)+C(3，3)=2^3-1=7. 所以如果我们知道对于数组中的每一个值知道其后面的值比他还大的有几个，那么这个问题就解决了。所以我们必须要有一个对应用于保存这个信息，
如下是简单代码，供参考：

public static void main(String[] args) {
		int[] array = new int[]{
				2,3,1,4
		};
		System.out.println(findCount(array));
	}
	
	public static int findCount(int[] array){
		int[] countArray = new int[array.length];
		// NlogN
		for (int i = 0; i < countArray.length; i++) {
			for (int j = i+1; j < countArray.length; j++) {
				if (array[j] > array[i]) {
					countArray[i] +=1;
				}
			}
		}
		int totalCount = 0;
		for (int i = 0; i < countArray.length; i++) {
			totalCount += ((1 << countArray[i])-1);
		}
		return totalCount;
	}

2014年9月05日 18:36

ieanwfg201
55
0 1 3

添加评论

0 0

public static int getSortNum(int[] a){
        int len = a.length;
        int num = 0;
        int before=0;
        for(int i=0;i<len;i++){
            before = a[i];
            for(int j=i+1;j<len;j++){
                if(before < a[j]){
                    num++;
                    before = a[j];
                }
            }
        }
        return num;
    }

2014年9月05日 09:48

Transy
30
0 0 0

1条评论

0 0

问题的关键在于：需要知道数组中的每个元素之后，比该数组大的元素有多少个。
比如[2,3,1,4] 能够在N*log(N)复杂度之内计算出 2-->2个， 3 --> 1个， 1-->1个，4 --> 0个。如果知道了每个元素后面有多少个大于该元素的，那么以该元素开头的顺序序列也是固定的，为大于元素个数的数目（在不允许跨index的情况下）。

基本的思想，利用复杂度为N*LogN的排序，这个是比较容易的，比如快速排序。但是需要在排序的时候得出每个元素后面有多少个比自己大的。这里给出一个基于冒泡的（使用快速排序有可能不行）

1. 使用一个Map<元素, 元素后有多少个大于自己的>, 初始化对于Ai为<Ai, N-i>

2.开始冒泡，对于每次交换行为：
     比如Aj <---> Aj+1的交换，将Aj对应的计数减一，即Map.set(Ai,Map.get(Aj) - 1)

3.针对Map中的每个元素，根据计数的Value确定组合的个数，整体加和即为最终的结果。

思路：初始认为每个元素后面的所有元素都比自己大，每次发生交换行为，则证明比自己大的元素少了一个，这样交换完毕以后就知道有多少个元素比自己大了。

比如[2,3,1,4]初始<(2,3),(3,2),(1,1),(4,0)>
冒泡：2开始， 2,3不交换，3,1交换，1,4不交换，Map为<(2,3),(3,1),(1,1),(4,0)>
            2,1,3,4为交换完毕的数组
      第二轮：2,1交换2,3不交换，3,4不交换，Map为<(2,2),(3,1),(1,1),(4,0)>
           1,2,3,4为交换完毕数组，冒泡完毕。

组合(2,2)计算下来为2个
    (3,1)计算下来为1个
    (1,1)计算下来为1个
    (4,0)计算下来为0个。

共计4个。

复杂度评估：冒泡排序N*Log(N), Map的初始创建为N, Map每次操作为O(1), 因此总体的复杂度为 O(N*Log(N)) * O(1) + N = N * LogN

请题主看下是否可行。