Por ejemplo tengo esta matriz

int[] a = {6,10,16,11,7,12,3,9,8,5};

Quiero ordenar sus índices así

[6,9,0,4,8,7,1,3,5,2]

Entonces puedo usar índices para ordenar un valor del más pequeño al más grande. en mi código obtuve este lugar

[6, 9, 4, 8, 7, 4, 5, 6, 6, 6] 

Este es mi código

int[] a = {6,10,16,11,7,12,3,9,8,5};
int[] indeks = indekssortering(a);
System.out.println(Arrays.toString(indeks));

public static int[] indekssortering(int[] a){
    int[] indeks = new int[a.length];
    int m = 0;
    boolean finnes = false;
    boolean nyVerdi = false;
    int n = 0;
    for (int j = 0; j < a.length; j++) {
        for (int i = m+1; i < a.length ; i++) {
            if(a[m] > a[i]){
                for (int k = 0; k < j; k++) {
                    if(indeks[k] == i) finnes = true; //check if the same position is saved before
                }
                if(!finnes){ // if not so its the next minimum value
                    m = i;
                } else {
                    nyVerdi = true; // if didnt find match then the value used to compare is the next minimum
                }
            }
            finnes = false;
        }
        indeks[j] = m;
        if(nyVerdi) n=n+1;
        nyVerdi = false;
        m=0+n;
    }
    return indeks;
}

Necesito ayuda para que este código funcione o para encontrar una idea mejor que esta.

Lo que intenté hacer es. compare todos los valores con los primeros valores, obtenga el más pequeño y guarde la posición en la matriz (indeks). antes de guardarlo, hice un bucle para verificar si esta posición se ha agregado antes. y si no hay un valor mayor que el valor utilizado para comparar, eso significa que es el próximo valor pequeño. Tengo algunos de ellos bien y otros mal. Creo que necesito cambiar esta idea y encontrar una mejor solución.

2
hussein albirouti 16 sep. 2018 a las 17:11

6 respuestas

La mejor respuesta

Aquí una implementación clásica del algoritmo de clasificación de burbujas modificada para clasificar índices

Lo que está buscando es en realidad cualquier algoritmo de clasificación que clasifique int [] array. Es una lista interminable de implementaciones en todo Internet. Y luego simplemente cambie la comparación a array[result[i]] e intercambie los valores en result no en array itseft.

static int[] sort(int[] array) {
    final int size = array.length;

    final int[] result = new int[size];
    for (int i = 0; i < size; i++)
        result[i] = i;

    boolean sorted;
    do {
        sorted = true;
        int bubble = result[0];
        for (int i = 0; i < size - 1; i++) {
            if (array[bubble] > array[result[i + 1]]) {
                result[i] = result[i + 1];
                result[i + 1] = bubble;
                sorted = false;
            } else {
                bubble = result[i + 1];
            }
        }
    } while (!sorted);

    return result;
}

result arrays for your input data is [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]
3
Maxim 16 sep. 2018 a las 15:38

Con java 8, puede usar una comparación lambda. Opcionalmente, puede hacer un reordenamiento in situ de [] e I [] de acuerdo con I [].

package x;
import java.util.Arrays;
public class x {
    // although I[] needs to be of type Integer, a[] doesn't
    public static void main(String[] args) {
        int[] a = {6,10,16,11,7,12,3,9,8,5};
        // generate array of indices
        Integer[] I = new Integer [a.length];
        for(int i = 0; i < I.length; i++)
            I[i] = i;
        // sort I[] according to a[]
        Arrays.sort(I, (i, j) -> a[i]-a[j]);
        // display result
        for (int i = 0; i < a.length; i++)
            System.out.println(a[I[i]]);

        // optional inplace reorder a[] and I[] according to I[]
        // time complexity is O(n)
        for(int i = 0; i < I.length; i++){
            if(i != I[i]){
                int t = a[i];
                int j;
                int k = i;
                while(i != (j = I[k])){
                    a[k] = a[j];
                    I[k] = k;
                    k = j;
                }
                a[k] = t;
                I[k] = k;
            }
        }
        // display result
        System.out.println();
        for (int i = 0; i < a.length; i++)
            System.out.println(a[i]);
    }
}
0
rcgldr 16 sep. 2018 a las 17:55

Aquí hay una solución sin y con Java 8 Stream API.

import java.util.*;
import java.util.stream.IntStream;

public class SortIndices {

    static class Indexed {
        private final int number;
        private final int index;

        Indexed(int number, int index) {
            this.number = number;
            this.index = index;
        }

        public int getNumber() {
            return number;
        }

        public int getIndex() {
            return index;
        }
    }

    static int[] indexesSorted(int[] input) {
        // Without using Stream API
        List<Indexed> indexed = new ArrayList<>();
        for(int i = 0; i < input.length; ++i) {
            indexed.add(new Indexed(input[i], i));
        }
        Collections.sort(indexed, Comparator.comparing(it -> it.number));
        int[] result = new int[indexed.size()];
        for(int i = 0; i < input.length; ++i) {
            result[i] = indexed.get(i).index;
        }
        return result;
        // Using Stream API
        /*return IntStream.range(0, input.length)
                .mapToObj(i -> new Indexed(input[i], i))
                .sorted(Comparator.comparing(it -> it.number))
                .mapToInt(it -> it.index)
                .toArray();*/
    }

    public static void main(String[] args) {
        int[] result = indexesSorted(new int[]{6, 10, 16, 11, 7, 12, 3, 9, 8, 5});
        System.out.println(Arrays.toString(result));
    }
}

Si no puede usar Java 8, puede implementar la interfaz Comparable en Indexed

    static class Indexed implements Comparable<Indexed> {
        private final int number;
        private final int index;

        Indexed(int number, int index) {
            this.number = number;
            this.index = index;
        }

        public int getNumber() {
            return number;
        }

        public int getIndex() {
            return index;
        }

        @Override
        public int compareTo(Indexed o) {
            return Integer.compare(number, o.number);
        }
    }

Y luego llame a Collections.sort sin segundo argumento.

3
tdelev 16 sep. 2018 a las 14:46

Si hay disponible una biblioteca para indexOf(int[], int) (como Guava), puede obtenerla muy fácilmente:

int[] a = { 6, 10, 16, 11, 7, 12, 3, 9, 8, 5 };
int[] b = Arrays.copyOf(a, a.length);
Arrays.sort(b);
Arrays.setAll(b, i -> indexOf(a, b[i])); // b = [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]

Si no hay una biblioteca disponible, aquí hay una implementación indexOf(int[], int):

public static int indexOf(int[] array, int search) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == search) {
            return i;
        }
    }
    return -1;
}
0
steffen 16 sep. 2018 a las 16:14

Básicamente, está buscando una permutación de la matriz. Específicamente, para una permutación de clasificación.

Desafortunadamente, la notación es algo ambigua y confusa cuando se refiere a índices. La principal diferencia es si

sorted[indices[i]] = array[i]

O

sorted[i] = array[indices[i]]

Debería producir la matriz ordenada. Según su pregunta, está buscando lo último.

Esto se puede implementar de diferentes maneras, ya sea colocando los elementos en un List<Integer> y ordenando esta lista usando un comparador que se refiere a la matriz original, o ordenando una lista de "pares", cada uno de los cuales consiste en el valor y Su índice original. (Este enfoque ya fue mostrado básicamente por tdelev en su respuesta)

Aquí hay una implementación que computa explícitamente la matriz de índice y la aplica como una permutación a la matriz de entrada:

import java.util.Arrays;
import java.util.Comparator;
import java.util.function.IntBinaryOperator;

public class SortingPermutations
{
    public static void main(String[] args)
    {
        int[] a = {6,10,16,11,7,12,3,9,8,5} ;
        int[] p = computeAscendingSortingPermutation(a);
        int[] s = applyPermutation(a, p);

        System.out.println("array       : " + Arrays.toString(a));
        System.out.println("permutation : " + Arrays.toString(p));
        System.out.println("sorted      : " + Arrays.toString(s));
    }

    /**
     * Compute the sorting permutation for the given array. This will return 
     * an array <code>p</code> so that <code>sorted[i] = array[p[i]]</code>
     * will result in an array where the values are sorted in ascending order.
     * 
     * @param array The array
     * @return The sorting permutation
     */
    private static int[] computeAscendingSortingPermutation(int array[])
    {
        return computeSortingPermutation(array, Integer::compare);
    }

    /**
     * Compute the sorting permutation for the given array. This will return 
     * an array <code>p</code> so that <code>sorted[i] = array[p[i]]</code>
     * will result in an array where the values are sorted according to
     * the given comparator
     * 
     * @param array The array
     * @param intComparator The comparator for the integer values
     * @return The sorting permutation
     */
    private static int[] computeSortingPermutation(
        int array[], IntBinaryOperator intComparator)
    {
        class Entry
        {
            int value;
            int index;
        }
        int n = array.length;
        Entry entries[] = new Entry[n];
        for (int i = 0; i < n; i++)
        {
            Entry e = new Entry();
            e.value = array[i];
            e.index = i;
            entries[i] = e;
        }
        Comparator<Entry> comparator = 
            (e0, e1) -> intComparator.applyAsInt(e0.value, e1.value);
        Arrays.sort(entries, comparator);
        int result[] = new int[n];
        for (int i = 0; i < n; i++)
        {
            Entry e = entries[i];
            result[i] = e.index;
        }
        return result;
    }


    /**
     * Apply the given permutation to the given array, and return the result
     * as a new array. The result will be an array <code>r</code> where
     * <code>r[i] = array[permutation[i]]</code>
     * 
     * @param array The input array
     * @param permutation The permutation
     * @return The result array
     */
    private static int[] applyPermutation(int array[], int permutation[])
    {
        int n = array.length;
        int result[] = new int[n];
        for (int i=0; i<n; i++) 
        {
            result[i] = array[permutation[i]];
        }
        return result;
    }

}

La salida es

array       : [6, 10, 16, 11, 7, 12, 3, 9, 8, 5]
permutation : [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]
sorted      : [3, 5, 6, 7, 8, 9, 10, 11, 12, 16]

Como se esperaba.

0
Marco13 16 sep. 2018 a las 17:31
  • Use un Map. Deje que key sea el elemento y value sea un queue de indices en el que ocurrió para ese valor.

  • Ordenar la matriz. Ahora, sondee cada elemento de su cola almacenada en el mapa.

  • Complejidad de tiempo: O (n * log (n))

  • Complejidad espacial: O (n)

Código:

import java.util.*;
public class Solution {
    public static void main(String[] args){
        int[] a = new int[]{6,10,16,11,7,12,3,9,8,5};
        int[] result = new int[a.length];
        Map<Integer,Queue<Integer>> map = new HashMap<>();
        for(int i=0;i<a.length;++i){
            if(map.containsKey(a[i])){
                map.get(a[i]).offer(i);
            }else{
                Queue<Integer> q = new LinkedList<Integer>();
                q.offer(i);
                map.put(a[i],q);
            }
        }

        Arrays.sort(a);
        for(int i=0;i<result.length;++i){
            result[i] = map.get(a[i]).poll();
        }

        System.out.println(Arrays.toString(result));
    }
}

SALIDA:

[6, 9, 0, 4, 8, 7, 1, 3, 5, 2]
0
vivek_23 16 sep. 2018 a las 16:35