在一个阵列重新排列偶数和奇数 [英] Rearrange even and odd in an array

问题描述

我已编写的程序来放置所述阵列的左侧和奇数那些所有偶数元素到阵列的右半部。元素的顺序是令人关注的不是。我想知道是否有更高效的算法比这一点。我的最坏情况复杂度为O（n / 2）。这里是code。

  //程序却将所有的偶数阵列中的左奇的权利。顺序的数字并不重要。

导入的java.util。*;
进口的java.lang。*;
进口java.io. *;


一流的重新排列
{
公共静态无效的主要（字串[] args）抛出java.lang.Exception的
{
    //你的code到这里
    INT []数组=新INT [] {1,2,3,4,5,6,7};

    //保留两个指针。
    诠释奇数，偶数;
    奇= 0;
    即使= array.length-1;
    INT I;

    // code，重新安排数组的内容
    I = 0;
    而（I＆LT; array.length）{
        如果（数组[我]％2！= 0）{
            奇=我;
            打破;
        }
        我++;
    }

    I = array.length-1;
    而（ⅰ＆GT; = 0）{
        如果（数组[我]％2 == 0）{
            即使=我;
            打破;
        }
        一世 - ;
    }

    而（奇数LT;偶数）{
        如果（（数组[奇]％2 = 0）及！及（数组[甚至]％2 == 0））{
            //交换的内容
            阵列[奇] =阵列[奇] +阵列[甚至]
            阵列[甚至] =阵列[奇]  - 阵列[甚至]
            阵列[奇] =阵列[奇]  - 阵列[甚至]
            奇++;
            甚至 - ;
        }

        否则，如果（阵列[奇]％2 == 0）{
            奇++;
        }

        否则，如果（阵列[甚至]％2！= 0）{
            甚至 - ;
        }

        其他
            继续;
    }
    对于（INT VAL：数组）
        的System.out.println（VAL +）;

}
}
 

解决方案

对于任何算法没有关于数据的结构，你不能做到这一点，在不到 O（N）足够的信息其中N是输入大小，因为如果你做得更快，这意味着你是不是考虑输入的一部分，因此算法可能是不正确的。

下面是就地$ C $下你的问题： -

  INT I = 0，J = N-1;

而（I＆LT; j）条{

  如果（ARR [I]％2 == 0）{

     我++;
  }

  其他 {

     掉期（ARR [我]，编曲[J]）;
     j--;

  }

}
 

I have written a program to place all even elements of the array to the left and odd ones to the right half of the array. The order of elements is not of concern. I was wondering if there is more efficient algorithm than this. My worst case complexity is O(n/2). Here is the code.

// Program to shift all even numbers in an array to left and odd to the right. Order of digits is not important.

import java.util.*;
import java.lang.*;
import java.io.*;


class Rearrange
{
public static void main (String[] args) throws java.lang.Exception
{
    // your code goes here
    int[] array = new int[] {1,2,3,4,5,6,7};

    // keep two pointers.
    int odd, even;
    odd = 0; 
    even = array.length-1;
    int i;

    // Code to re-arrange the contents of the array
    i=0;
    while(i<array.length){
        if(array[i]%2!=0){
            odd = i;
            break;
        }
        i++;    
    }

    i=array.length-1;
    while(i>=0){
        if(array[i]%2==0){
            even = i;
            break;
        }
        i--;    
    }

    while(odd<even){
        if((array[odd]%2!=0) && (array[even]%2==0)){
            // swap contents
            array[odd] = array[odd] + array[even];
            array[even] = array[odd] - array[even];
            array[odd] = array[odd] - array[even];
            odd++;
            even--;
        }

        else if(array[odd]%2==0){
            odd++;
        }

        else if(array[even]%2!=0){
            even--;
        }

        else
            continue;
    }
    for(int val : array)
        System.out.println(val+" ");

}
}

解决方案

For any algorithm without sufficient information about structure of data you cannot do it in less than O(N) where N is the input size because if you do it faster that means you are not considering a part of the input hence algorithm might be incorrect.

Here is in-place code for you problem :-

int i=0,j=n-1;

while(i<j) {

  if(arr[i]%2==0) {

     i++;
  }

  else {

     swap(arr[i],arr[j]);
     j--;

  }

} 

这篇关于在一个阵列重新排列偶数和奇数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！