0 
int[] array = {1,1,0,1,2,2,0,0};
int  firstNumber = 1;// dynamic can be 0 or 1 or 2
int numberOfOccurances = 0;

//Basic sort functionality
for(int i = 0 ; i< array.length; ++i)
{
    if(array[i] == firstNumber)
    {
        numberOfOccurances++;
    }
    for(int j = i+1; j<array.length; ++j)
    {   
        if(array[j] < array[i])
        {   
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}
int[] requiredArray= new int[array.length]; 
for(int i = array.length-1 ; i >= 0; i--)
{
    if(array[i] != firstNumber)
    requiredArray[i] = array[i];

}
for(int i =0;i<array.length;i++)
{
    if(i<numberOfOccurances)
    requiredArray[i]= firstNumber;
}

//Print Output
for (int i = 0; i<requiredArray.length; i++)
System.out.print(requiredArray[i] + "  ");

输出：1 1 1 1 0 0 2 2

我能够获得所需的输出，但我不确定这是否是解决我的问题的最佳方法？

4

3 回答 3

0

有个更好的方法。特别是，您的排序算法是

  1. 复杂度不是O(n^2)最优的O(n * log n)（实际上，您的语言的标准库无论如何都会包含一个很好的实现。
  2. 仍在处理n元素。如果你有很多“第一”，你实际上只需要 m = n - number_of_first元素，这可以在O(m * log m).

通常，第二点并不重要。如果是这样，您可能会处理一些不同的元素，然后使用类似的东西来获得更好的时间复杂性也是一个好主意https://en.wikipedia.org/wiki/Counting_sort

忽略几乎没有不同元素的情况，我建议您检查一次数组并将所有不是“firstNumber”的元素复制到另一个数组。然后，您使用标准排序算法对另一个数组进行排序 - 最好是内置算法。

最后，您的输出是array.length - otherArray.length时间，firstNumber然后是排序的内容otherArray

于 2015-10-15T15:29:06.993 回答
0

根据您的数字大小，您可能希望计算一个数字的每次出现并打印出您计算的次数。这是一个 O(n) 算法。

arrayToBeSorted = {collection of numbers}
firstNumber = arrayToBeSorted[0]
countArray = new int[max(arrayToBeSorted)]; //everything defaults to 0 in most languages
for i:= 0 -> N
    countArray[arrayToBeSorted[i]]++;

for i:= 0 ->countArray[firstNumber]
    print(firstNumber)

for i: = 0 ->countArray.length
    if (i == firstNumber)
        continue;
    for j:= 0 -> countArray[i]
        print(i)
于 2015-10-26T18:13:07.560 回答
0

这是一个简单的解决方案。在以下情况下更改号码： - 另一个是 firstNumber - 另一个是次要号码且不是第一个号码

    int[] array = {1,1,0,1,2,2,0,0,3,2,1,0,0,1,2,3,2,3};

    int firstNumber = 1, temp;

    for(int i=0;i<array.length-1;i++) {
        for(int j=i+1;j<array.length;j++) {

            if( (array[j] < array[i] && array[i]!=firstNumber) || array[j]==firstNumber) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
于 2015-10-15T12:43:53.090 回答