ordina una matrice per posizione relativa

Question

Assegna un array con numeri interi negativi e positivi, implementa un algoritmo che costa costa O (n) e spazi O (1) per rendere tutti gli interi negativi davanti a tutti gli interi positivi e mantenere la posizione relativa. per esempio: {1,7, -5,9, -12,15} -----> {-5, -12,1,7,9,15}

avete qualche idea?

Answer 1

Si sta richiedendo una funzione di partizione sul posto stabile.

La carta Stable Minimum Space Partitioning in Linear Time (1992) afferma di avere un tale algoritmo, ma alcuni SO questions hanno sollevato dubbi sulla sua fattibilità.

Answer 2

la mia idea di un algoritmo:

hanno un punto di rotazione simile alla selezione generale partizione in base. http://en.wikipedia.org/wiki/Selection_algorithm

ruotano intorno al perno scambiare valori finché tutti i numeri negativi sono in una partizione della matrice (con tutti i numeri positivi dopo che .. o forse circonda)

Tuttavia questo scambio avrà leggermente influenzata l'ordinamento . Spiegherò come correggere l'ordine dei numeri negativi (e si fa lo stesso per correggere l'ordine dei numeri positivi).

Ogni volta che hai scambiato due numeri, cambia il segno del numero.

significa che se si passa attraverso la partizione di numeri negativi, tutti quelli che sono positivi sono numeri negativi che sono stati scambiati. Ciò significa che tutti i numeri negativi tra un numero positivo e il successivo numero positivo devono essere prima del primo numero positivo. passare attraverso e li scambiare (non ci dovrebbero essere troppi in una fila così si dovrebbe ottenere 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. 

Answer 3

Questo codice è la maggior parte del tragitto .. Ho appena non hanno fatto il parte dove inverte i valori scambiati tra x, j e tra j, y. (puoi invertire la posizione ... non l'ho ancora fatto).

Comunque .. Io non ho tempo per completarlo ho paura, ma si spera che è possibile:

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 

ulteriore esempio:

_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] 

Answer 4

questo può essere fatto da alterando unire la funzione in un algoritmo di fusione.

Ingresso: int [] A, int basso, int metà, int alta

Loop in varianza prima dell'inizio: A [basso] A [metà] ha numeri -ve seguenti da + ve numeri e ha numeri che erano originariamente presenti in A [basso] in A [centro].
Sopra condizione vale per A [metà + 1] per Å []

passi Fusione:

1. saltare tutti gli elementi tra basso a metà che sono -ve, salvare il punto di partenza di + I numeri dicono nella variabile j.
2. copia elementi che sono già + rimanente prima metà di matrice temporanea
3. copia tutti gli elementi -ve nella gamma di metà + 1 a partire da una elevata [j], incrementando j
4. copiare gli elementi memorizzati in array temporaneo a continua da j

5. + ve elementi nella seconda metà di a sono già in atto, quindi non c'è bisogno di fare nulla

   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++; 
       } 
   }