例如，我有这个数组
int[] a = {6,10,16,11,7,12,3,9,8,5};
我想像这样排序它的索引
[6,9,0,4,8,7,1,3,5,2]
所以我可以使用索引从最小值到最大值进行排序。在我的代码中，我得到了这个
[6, 9, 4, 8, 7, 4, 5, 6, 6, 6]
这是我的代码
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;
}
我需要帮助才能使这个代码工作或找到比这更好的想法。
我试图做的是。将所有值与第一个值进行比较，得到最小值并将位置保存到数组中（凹凸）。在保存之前，我做了循环以检查之前是否添加了这个位置。如果没有大于用于比较的值的值，则意味着它的下一个小值。我有一些是对的，有些是错的。我相信我需要改变这个想法并找到更好的解决方案。
这里修改了经典的bubble sort algorithm实现以对索引进行排序
您正在寻找的实际上是任何排序int [] array的排序算法。它是遍布互联网的无穷无尽的实施列表。然后只需将比较更改为array[result[i]]并在result中交换值，而不是在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]
这是一个没有和使用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));
}
}
如果你不能使用Java 8，使用可以在Comparable上实现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);
}
}
然后在没有第二个参数的情况下调用Collections.sort。
如果有indexOf(int[], int)（如Guava）的库，你可以很容易地得到它：
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]
如果没有可用的库，这是一个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;
}
Map。让key成为元素，value成为queue的indices，在这个值上发生了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));
}
}
。码：
[6, 9, 0, 4, 8, 7, 1, 3, 5, 2]
OUTPUT：
permutation
你基本上是在寻找阵列的sorted[indices[i]] = array[i]
。具体而言，用于排序排列。
不幸的是，在引用索引时，符号有些含糊不清并且令人困惑。主要区别在于是否
sorted[i] = array[indices[i]]
要么
List<Integer>应该产生排序的数组。根据你的问题，你正在寻找后者。
这可以通过不同的方式实现，或者通过将元素放入tdelev in his answer并使用引用原始数组的比较器对该列表进行排序，或者通过对“对”列表进行排序，每个组由值和其原始索引组成。 （这种方法基本上已经由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;
}
}
展示）
这是一个显式计算索引数组的实现，并将其作为排列应用于输入数组：
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]
输出是
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]);
}
}
正如所料。
使用java 8，您可以使用lambda比较。或者，您可以根据I []对[]和I []进行原位重新排序。
qazxswpoi