1

我有一个我无法解决的面试问题。

用 Java 编程语言编写方法（不是程序），它将前半部分的所有偶数和奇数移动到整数数组的后半部分。

例如输入 = {3,8,12,5,9,21,6,10}; 输出 = {12,8,6,10,3,5,9,21}。

该方法应以整数数组为参数，并在同一个数组中移动项目（不要创建另一个数组）。这些数字可能与原始数组的顺序不同。这是算法测试，所以尽量给出尽可能高效的算法（可能是线性 O(n) 算法）。避免使用内置函数/API。*

还有一些关于什么是数据结构效率的基本介绍

4

14 回答 14

10

保留两个索引：一个到第一个奇数，一个到最后一个偶数。交换这些数字并更新索引。

于 2013-01-21T15:11:17.507 回答
6

（在@manu-fatto 的建议的帮助下）我相信这会做到：

private static int[] OddSort(int[] items)
{
    int oddPos, nextEvenPos;
    for (nextEvenPos = 0; 
         nextEvenPos < items.Length && items[nextEvenPos] % 2 == 0;
         nextEvenPos++) { }
    // nextEvenPos is now positioned at the first odd number in the array, 
    // i.e. it is the next place an even number will be placed

    // We already know that items[nextEvenPos] is odd (from the condition of the 
    // first loop), so we'll start looking for even numbers at nextEvenPos + 1
    for (oddPos = nextEvenPos + 1; oddPos < items.Length; oddPos++)
    {
        // If we find an even number
        if (items[oddPos] % 2 == 0)
        {
            // Swap the values
            int temp = items[nextEvenPos];
            items[nextEvenPos] = items[oddPos];
            items[oddPos] = temp;
            // And increment the location for the next even number
            nextEvenPos++;
        }
    }

    return items;
}

该算法恰好遍历列表 1 次（每个元素只检查一次），因此效率为 O(n)。

于 2013-01-21T15:40:08.793 回答
4

// 在一个 for 循环中执行此操作 

public static void evenodd(int[] integer) {

    int i = 0, temp = 0;
    int j = integer.length - 1;

    while (j >= i) {
        // swap if found odd even combo at i and j
        if (integer[i] % 2 != 0 && integer[j] % 2 == 0) {
            temp = integer[i];
            integer[i] = integer[j];
            integer[j] = temp;
            i++;
            j--;

        } else {
            if (integer[i] % 2 == 0) {
                i++;
            }
            if (integer[j] % 2 == 1) {
                j--;
            }

        }

    }
}
于 2013-10-22T10:25:11.463 回答
2

@JLRishe，

您的算法不保持顺序。举个简单的例子，比如 {1,5,2}，您将数组更改为 {2,5,1}。由于我是新用户并且缺乏声誉，因此我无法在您的帖子下方发表评论。

于 2014-06-03T07:07:10.353 回答
1 
public static void sorted(int [] integer) {

int i, j , temp;

for (i = 0;  i < integer.length;  i++) {

     if (integer[i] % 2 == 0) {
         for (j = i;  j < integer.length;  j++) {
              if (integer[j] % 2 == 1) {
                  temp = y[i];
                  y[i] = y[j];
                  y[j] = temp;
              }
          }
      }
      System.out.println(integer[i]);
}

public static void main(String args[]) {

       sorted(new int[]{1, 2,7, 9, 4}); 



}

}

答案是 1、7、9、2、4。

于 2013-07-05T03:47:29.273 回答
0

您可以通过在找到奇数项时将奇数项移动到数组末尾来使用单个循环来执行此操作。

static void EvensToLeft(int[] items) {
    int end = items.length;
    for (int i = 0; i < end; i++) {
        if (items[i] % 2) {
            int t = items[i];
            items[i--] = items[--end];
            items[end] = t;
        }
    }
}

给定一个长度为 n 的输入数组，内部循环恰好执行 n 次，并且只计算每个数组元素的奇偶校验一次。

于 2015-03-23T04:44:48.493 回答
0

难道是你被要求实现一个非常基本的 BubbleSort 版本，其中元素 e 的排序值，其中 e = arr[i], = e%2==1 ？1：-1？问候莱昂

于 2013-01-21T15:14:32.273 回答
0 
class Demo
{
public void sortArray(int[] a)
{
int len=a.length;
int j=len-1;
for(int i=0;i<len/2+1;i++)
{
if(a[i]%2!=0)
{
while(a[j]%2!=0 && j>(len/2)-1)
j--;
if(j<=(len/2)-1)
break;
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
}
for(int i=0;i<len;i++)
System.out.println(a[i]);
}

public static void main(String s[])
{
int a[]=new int[10];
System.out.println("Enter 10 numbers");
java.util.Scanner sc=new java.util.Scanner(System.in);
for(int i=0;i<10;i++)
{
a[i]=sc.nextInt();
}
new Demo().sortArray(a);
}
}
于 2013-10-22T11:32:00.217 回答
0 
private static void rearrange(int[] a) {
    int i,j,temp;
    for(i = 0, j = a.length - 1; i < j ;i++,j--) {
        while(a[i]%2 == 0 && i != a.length - 1) {
            i++;
        }
        while(a[j]%2 == 1 && j != 0) {
            j--;
        }
        if(i>j)
            break;
        else {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }       
}
于 2014-08-07T02:45:13.067 回答
0 
public void sortEvenOddIntegerArray(int[] intArray){
    boolean loopRequired = false;
    do{
        loopRequired = false;
        for(int i = 0;i<intArray.length-1;i++){

            if(intArray[i] % 2 != 0 && intArray[i+1] % 2 == 0){

                int temp = intArray[i];
                intArray[i] = intArray[i+1];
                intArray[i+1] = temp;
                loopRequired = true;
            }
        }
    }while(loopRequired);
}
于 2014-12-10T21:27:55.053 回答
0

公共类 ArraysSortEvensFirst {

public static void main(String[] args) {
    int[] arr = generateTestData();
    System.out.println(Arrays.toString(arr));

    ArraysSortEvensFirst test = new ArraysSortEvensFirst();
    test.sortEvensFirst(arr);

}

private static int[] generateTestData() {
    int[] arr = {1,3,5,6,9,2,4,5,7};
    return arr;
}

public int[] sortEvensFirst(int[] arr) {
    int end = arr.length;

    int last = arr.length-1;
    for(int i=0; i < arr.length; i++) {
        // find odd elements, then move to even slots
        if(arr[i]%2 > 0) {
            int k = findEven(last, arr);
            if(k > i) swap(arr, i, k);
            last = k;
        }
    }

    System.out.println(Arrays.toString(arr));
    return arr;
}

public int findEven(int last, int[] arr) {
    for(int k = last; k > 0; k--) {
        if(arr[k]%2 == 0) {
            return k;
        }
    }
    return -1; // not found;
}

public void swap(int[] arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

}

输出： [1, 3, 5, 6, 9, 2, 4, 5, 7] [4, 2, 6, 5, 9, 3, 1, 5, 7]

于 2016-12-14T07:36:12.300 回答
0

公共类 SeperatOddAndEvenInList {

public static int[] seperatOddAndEvnNos(int[] listOfNumbers) {
    int oddNumPointer = 0;
    int evenNumPointer = listOfNumbers.length - 1;
    while(oddNumPointer <= evenNumPointer) {                
            if(listOfNumbers[oddNumPointer] % 2 == 0) { //even number, swap to front of last known even number
                int temp;
                temp = listOfNumbers[oddNumPointer];
                listOfNumbers[oddNumPointer] = listOfNumbers[evenNumPointer];
                listOfNumbers[evenNumPointer] = temp;
                evenNumPointer--;
            }
            else {  //odd number, go ahead... capture next element
                oddNumPointer++;
            }


    }
    return listOfNumbers;
}


public static void main(String[] args) {
    // TODO Auto-generated method stub
    int []arr = {3, 8, 12, 5, 9, 21, 6, 10};
    int[] seperatedArray = seperatOddAndEvnNos(arr);
    for (int i : seperatedArray) {
        System.out.println(i);
    }

}

}

于 2016-05-15T00:13:41.123 回答
0

使用两个计数器 i=0 和 j=a.length-1 并不断交换位于错误位置的偶数和奇数元素。

  public int[] evenOddSort(int[] a) {
        int i = 0;
        int j = a.length - 1;
        int temp;
        while (i < j) {
            if (a[i] % 2 == 0) {
                i++;
            } else if (a[j] % 2 != 0) {
                j--;
            } else {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        return a;
    }
于 2016-01-18T03:52:53.583 回答
0

效率为 O(log n)。

public class TestProg {
public static void main(String[] args) {
    int[] input = { 32, 54, 35, 18, 23, 17, 2 };
    int front = 0;
    int mid = input.length - 1;
    for (int start = 0; start < input.length; start++) {
    //if current element is odd
        if (start < mid && input[start] % 2 == 1) {
    //swapping element is also odd?
            if (input[mid] % 2 == 1) {
                mid--;
                start--;
            } 
    //swapping element is not odd then swap
     else {
                int tmp = input[mid];
                input[mid] = input[start];
                input[start] = tmp;
                mid--;
            }
        }

    }
    for (int x : input)
        System.out.print(x + " ");
}

}

于 2016-11-21T12:23:04.393 回答