"Chiziqlardan" juft sonlarni chiqarish va oldinga oldinga surish

Birinchidan - bu uy vazifasi emas - men bu savolni oxirgi intervyuda oldim va uni tugatolmadim.

Shunday qilib, savol quyidagicha edi: "n n uzunligi bo'lgan int majmuasi berilgan bo'lsa," barcha raqamlarni olib tashlang va g'alati narsalarni oldinga olib boring ". Bu so'zlarni eshitib qolishdi, chunki ular olib tashlashdi, ammo misollar ko'rsatdiki, faqat bitta raqamni oldingi qatorga qo'yish kerak (0-indeksdan boshlab) va hatto raqamlar qatorda qolishi mumkin (yoki emas - bu muhim emas) ) barcha g'alati raqamlardan keyin. Misol:

{1, 4, 6, 8, 7, 2} -> {1, 7, whatever}
{2, 4, 6, 9, 5} -> {9, 5, whatever}

Men imkon qadar samarali bo'lishni xohlayman. Hech qanday qo'shimcha kutubxona yoki vaqtinchalik qatorlarni ishlata olmadim.

Hozirgacha bu bor, lekin men siqilganman:

private static void removeEven(int[] k, int n) {
for (int i = 0; i < n; i++) {
  if (k[i] % 2 == 0) {
    k[i] =//don't know
  }
}
3
u bir xil qator bo'lishi kerak.
qo'shib qo'ydi muallif ohwelppp, manba

6 javoblar

Mana bu yechim:

 private static int[] removeEven(int[] k, int n) {
            for (int i = 0; i < n; i++) {
              if (k[i] % 2 == 0) {
                  for(int j=i+1; j
1
qo'shib qo'ydi

O'ylaymanki, ikkita o'zgaruvchini qatorda joylashgan joylarga ko'rsatar edim. Bitta keyingi raqamni (boshidan boshlab) ko'rsatish mumkin, va keyingi navbatdagi songa ishora qiladi (oxiridan boshlab). Keyingi navbatdagi raqam keyingi songa qaraganda past ko'rsatkichga ega bo'lsa-da, ularni o'zgartiring. Bu erda ishlaydigan va sinov qilingan kod:

public static void main(String[] args) {
    int[] test = {2, 4, 6, 9, 5};
    int currentEven = -1;
    int currentOdd = test.length;
    while (currentEven < currentOdd) {
        currentEven = nextEvenIndex(currentEven + 1, test);
        currentOdd = nextLastOddIndex(currentOdd - 1, test);

        if (currentEven < currentOdd) {
            swap(currentOdd, currentEven, test);
        }
    }

    for (int i = 0; i < test.length; i++) {
        System.out.print(test[i]);
    }
}

private static int nextEvenIndex(int start, int[] array) {
    while (start < array.length) {
        if (array[start] % 2 == 0) {
            return start;
        }
        start++;
    }
    return -1;
}

private static int nextLastOddIndex(int start, int[] array) {
    while (start >= 0) {
        if (array[start] % 2 == 1) {
            return start;
        }
        start--;
    }
    return -1;
}

private static void swap(int index1, int index2, int[] array) {
    int swap = array[index1];
    array[index1] = array[index2];
    array[index2] = swap;
}

Bu O (n), bu eng yaxshi ish, deb o'ylayman bu yerga.

Bu boshqa ko'plab boshqa javoblardan ham yaxshiroq ishlaydi, chunki raqam ikki marta almashtirilmaydi; ya'ni boshqa echimlarning aksariyati butun majmuani o'zgartiradi (ba'zan keraksiz svoplarni hosil qiladi), bu esa faqatgina yarmidan ko'pini o'zgartiradi.

1
qo'shib qo'ydi

Qaytish qatori pozitsiyasini eslab qolish uchun loop ichida hisoblagich kerak. Qolgan qator qatorni 0 ga qo'yish uchun ushbu kodni ishlatganman.

private static void removeEven(int[] k, int n) {
    int counter = 0;
    for (int i = 0; i < n; i++) 
        if (k[i] % 2 == 1)
            k[counter++] = k[i];
    for (int i=counter; i

Umid qilamanki, bu sizga javob beradi!

1
qo'shib qo'ydi
Yo'q, men uni echib olib, g'alati narsalarni oldimga qo'yaman. Iltimos, kodimni bajarishga urinib ko'ring va natijada siz so'ragan narsangiz bilan bir xil bo'ladi!
qo'shib qo'ydi muallif delca85, manba
Siz oldingilarini oldinga qo'yasiz!
qo'shib qo'ydi muallif Mehdi, manba

Men bu usulni o'zgartirgan bo'lar edim, men uni yo'q qilishni emas, balki g'alati narsalarni oldga ko'chiradigan narsalarni o'zgartirar edim, ular esa ular qatorida qoldirilgan narsalar haqida qayg'urmaydi, shuning uchun mening yondashuvim

private static int moveOddToFront(int[] k) {
    int frontIndex = 0;
    for (int i = 0; i < k.length; i++) {
        boolean isOdd = k[i] % 2 != 0;
        if (isOdd) {
            k[frontIndex] = k[i];
            frontIndex++;
        }
    }

    int newSize = frontIndex;
    return newSize;
}
1
qo'shib qo'ydi
Kechirasiz, lekin bu faqat ishlamaydi. Men buni {5, 4, 3, 8, 6, 4, 9, 7,6} bilan sinab ko'rdim va natijada {5, 3, 9, 7, 6, 4, 9, 7, 6).
qo'shib qo'ydi muallif dsp_user, manba
To'g'ri javob faqatgina yuqorida keltirilgan qatorni emas, butun qator uzunligini qamrab oladi. Yaxshiyamki, hozir juda muhim emas.
qo'shib qo'ydi muallif dsp_user, manba
OK, hatto tekis elementlarni butunlay e'tiborsiz qoldiradigan bo'lsa, sizning yechimingiz ishlaydi. Ko'rib chiqayapman, ba'zi echimlar hatto elementlarni ham e'tibordan chetda qoldirmaydi.
qo'shib qo'ydi muallif dsp_user, manba
Agar siz asl nizomga qarasangiz, ular sizning raqamingizning old qismiga joylashtirilganidan keyin 4 ta raqamga ega ekanligingizni ko'rasiz va yangi o'lcham 4 bo'lsa, savolda {odd raqamlar, nima bo'lsa}
qo'shib qo'ydi muallif Mehdi, manba
Bu savolga javob beradigan narsalarni tushunmayapman, agar siz qolgan qatorlardan xavotirlansangiz, u holda ularni 0 yoki har qanday qilishingiz mumkin. Savolga ko'ra, bu qatorning qolgan qismi haqida qayg'urmaydi. Iltimos, batafsilroq tushuntiring
qo'shib qo'ydi muallif Mehdi, manba

Birinchidan, qatorni qaytarib oladigan quyidagi qator soxta kodga o'xshash narsa qanday bo'ladi: birinchisi, yakunlanadi va yagona va hatto altkümelerin asl tartibini saqlab qoladi.

if array.length < 2 
  return array
else
  p=0
  while array[p].odd and p < array.length
    p++
  q = p+1
  if q < array.length
    repeat
      if array[q].odd
        swap(array,p,q) p++ q++
      else
        q++
    until q >= array.length
0
qo'shib qo'ydi

Qiymatni harakatga o'tkazadigan joyni belgilash uchun boshqa o'zgarmaydiganni ishlatishdan ko'ra, qiymatni o'zgartiradigan vaqtinchalik o'zgaruvchidan foydalanishingiz mumkin.

Kod:

for (int i = 0, j = 0; i < n; i++) {
        if (k[i] % 2 != 0 ) {
            int tempInt = k[j];
            k[j] = k[i];
            k[i] = tempInt;
            j++;
        }
    }
0
qo'shib qo'ydi