logo标签列表

按照相对位置排序数组

algorithmpositionsorting
5
给定一个包含正负整数的数组，编写一个算法，时间复杂度为 O(n)，空间复杂度为 O(1)，将所有负整数移动到正整数之前并保持相对位置不变。 例如：{1,7,-5,9,-12,15} -----> {-5,-12,1,7,9,15} 你有什么想法吗？
请参考以下程序相关内容：http://blog.csdn.net/v_july_v/article/details/7329314 - lzj509649444
4个回答
5
1
论文引用：“此外，我们假设有一个恒定数量的额外存储位置，每个位置都能够存储O(log2n)位的单词。”我不知道他们为什么称之为O(1)的额外空间。 - Reinstate Monica
1

我对算法的想法：

有一个类似于基于分区的普通选择中的枢轴点。http://en.wikipedia.org/wiki/Selection_algorithm

绕枢轴点旋转，交换值，直到所有负数在数组的一个分区中（之后是所有正数，或者可能围绕它）

但是这种交换会略微影响顺序。 我将解释如何纠正负数的排序（您也可以纠正正数的排序）。

每次交换两个数字时..更改数字的符号。

这意味着如果您通过负数分区，则所有为正数的数字都是交换过的负数。这意味着在正数和下一个正数之间的所有负数应该在第一个正数之前。遍历并交换它们所有（一次不会太多，因此您应该获得O（N））

negs = -4,-5,-6
pos = 1,2,3
ans = -4,-5,-6,1,2,3

1,2,-4,-5,3,-6

i->-4  j->-5
-4 and -5 are both negative.. decrease i by one

1,2,-4,-5,3,-6
i->2 j->-5
swap.

1,5,-4,-2,3,-6
i->1 j->3
1 and 3 are both positive, increase j by one (take turns at changing i,j)

1,5,-4,-2,3,-6
i->1 j->-6
swap.

6,5,-4,-2,3,-1

#now we have negs at start, pos at end of array.
#now do corrections using signs as notification of what was swapped
#we had a counter that told us there were 3 negs.and 3 pos.
#fix first 3 negs.. 6,5,-4 should go to -4,-5,-6
(can tell order by. non swapped negs always come before swapped negs..in the order they are in.. negs are in reverse order)
i'll leave you to implement algorithm for it.
你能看出如何把6,5,-4变成-4,-5,-6吗？-4应该首先出现，因为它还没有被交换。6,5在逆序中跟在-4后面（因为交换会使它们翻转）。所以你的算法只需要从左到右遍历列表，将翻转的元素交换到末尾，并在每次交换时将末尾减1。然后将未翻转的元素移动到前面的位置。 - Rusty Rob
非交换的负数总是出现在交换的负数之前。我不这么认为，例如1，-4，2，-5，3，-6-->(i=2，j=-5，交换为[1，-4，5，-2，3，-6]) --> (i=-4，j=3，然后将j增加一并将i减少一，i=1，j=-6，交换为[6，-4，5，-2，3，-1]），然后修复3个负数[6，-4，5]--->(i=6，j=-4，交换为[4，-6，5]，然后到[-4，-6，-5]）。因此，未交换和已交换的数字混合在一起，如何才能得到正确的结果？顺便说一下，这个算法的时间复杂度将是O(nlogn)，而不是O(n)，因为您需要每次遍历所有左侧数字，T(2n)=2T(n)+n=nlogn。 - lzj509649444
我的算法中得到[6，-4，5]的部分是O（N）。现在你需要将负数移到前面，并反转正数并将它们移到后面以获得[-4，5，6]，这就是答案。我声称这最后一步也可以在O（N）时间内原地完成。我在代码末尾正在研究它，但没有时间完成它。 - Rusty Rob
你能给出修复[6，-4，5]的步骤吗？我认为它需要递归地进行修复，以便时间成本不是O（n）。例如，更大的负面方面是[6，-4，5，-3，7]，如何使用相同的算法以在O（n）时间内获得正确答案？ - lzj509649444
1
我必须说谢谢。你不仅提供了你的想法，而且还实现了它们。这就是我从你身上学到的认真态度。和你讨论很愉快。 - lzj509649444
显示剩余4条评论
0

这段代码已经完成了大部分工作，只是还没有实现将x、j之间以及j、y之间交换的值反转的部分（你可以原地反转..我还没有做到）。

无论如何，我很抱歉没有时间来完成它，但希望你能够完成：

def brute_force(nums):
    neg = [i for i in nums if i<0]
    pos = [i for i in nums if i>=0]
    return neg+pos

def in_place(nums,i,j,depth):
    x,y = i,j
    print 'running on ',nums[i:j+1]
    if j-i==1:
        a,b = nums[i],nums[j]
        if a>=0 and b<0:
            nums[i],nums[j] = b,a
        return None
    #print i,j
    while i<j:
        a,b = nums[i],nums[j]
        if (a<0 and b>=0):
            i+=1
            j-=1
        elif (a>=0 and b<0):
            nums[i],nums[j]=-b,-a
            i+=1
            j-=1
        elif a<0:
            i+=1
        else:
            j-=1
    print "changed1 to ", nums
    print nums[x:j+1],nums[j+1:y+1]
    start = (i for i in reversed(nums[x:j+1]) if i>=0)
    for i in range(x,j):
        if nums[i]>=0:
            nums[i]=next(start)
    print "changed2 to ", nums
    end = (i for i in reversed(nums[j+1:y+1]) if i<0)
    for i in range(j+1,y+1):
        if nums[i]<0:
            nums[i]=next(end)
    print "changed3 to ", nums
    if depth == 0:
        in_place(nums,0,j,depth+1)
        in_place(nums,j+1,len(nums)-1,depth+1)







nums = [1,2,-4,-5,3,-6]

print brute_force(nums)
in_place(nums,0,len(nums)-1,0)
print nums
print "going z"
#z = [-2,3,-1]
#in_place(z,0,2,0)
#print z

更进一步的例子：

_list = [1,-4,2,-5,3,-6]

def in_place(nums,i,j,depth):
    x,y = i,j
    print 'running on ',nums[i:j+1]
    if j-i==1:
        a,b = nums[i],nums[j]
        if a>=0 and b<0:
            nums[i],nums[j] = b,a
        return None
    #print i,j
    while i<j:
        a,b = nums[i],nums[j]
        if (a<0 and b>=0):
            i+=1
            j-=1
        elif (a>=0 and b<0):
            nums[i],nums[j]=-b,-a
            i+=1
            j-=1
        elif a<0:
            i+=1
        else:
            j-=1
    print "changed1 to ", nums

in_place(_list,0,len(_list)-1,0)

>>>
running on  [1, -4, 2, -5, 3, -6]
changed1 to  [6, -4, 5, -2, 3, -1]
0

这可以通过 修改归并排序中的归并函数 算法来完成。

输入：int [] A，int low，int mid，int high

循环不变式启动前： A [low] 到 A [mid] 有负数，然后是正数，并且具有最初存在于 A [low] 到 A [mid] 中的数字。
上述条件适用于 A [mid + 1] 到 A [high]

合并步骤:

  1. 跳过low到mid之间所有负数的元素，保存正数的起始点在变量j中。
  2. 将mid之前的所有正数剩余元素复制到临时数组中
  3. 从A[j]开始复制mid+1到high范围内的所有负数元素，同时递增j
  4. 将存储在临时数组中的元素复制回A，继续从j处进行

  5. A的第二半部分中的正数元素已经就位，因此不需要做任何操作

    public static void rearrange(int[] a){
    merge_arrange(a, 0, a.length-1);
}

public static void merge_arrange(int[] a, int low, int high){
    if(low < high){
        int mid = (low+high)/2;
        merge_arrange(a, low, mid);
        merge_arrange(a, mid+1, high);

        merge(a, low, mid, high);
    }
}

public static void merge(int[] a, int low, int mid, int high){
    ArrayList<Integer> temp = new ArrayList<Integer>();

    int i;
    for(i=low;i<=mid && a[i]<0;i++);

    int j=i;
    while(i<=mid){
        temp.add(a[i++]);
    }

    int k;
    for(k=mid+1;k<=high && a[k]<0;k++){
        a[j] = a[k];
        j++;
    }

    for(int num:temp){
        a[j] = num;
        j++;
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接