剣はoffer(12,13)の数値の整数の次数を指して、配列の順序を調整して奇数を偶数の前に位置させます

1.数値の整数次数
時間制限:1秒空間制限:32768 Kテーマは、与えられたdoubleタイプの浮動小数点数baseとintタイプの整数exponentを記述する.baseのexponent次数を求めます.
標準の高速べき乗...注意baseは0 return 0で、私はJSで間違いを投げてojの上でQQQを間違えてまた負数の情況があって、正になって、それから逆戻りします.実はこのbaseはdoubleタイプで、C++の中の話は直接比較することができなくて、absを書く必要があります

    boolean equal(double num1,double num2){
        if(num1-num2>-0.000001&&num1-num2<0.000001)
            return true;
        else
            return false;
    }

私はjsで書くとまずこの問題を考えない.あとは高速べき乗の思想で、実はバイナリ化して答えを再編成して、答えを再編する時底数は新しいbaseです.時間複雑度はバイナリの長さ,すなわちlognである.(参照ツリーの深さ)

/*
2^11 = 2^1 * 2^2 * 2^8
2^1011 = 1* 2^0001 + 1* 2^0010 + 0*2^0000 +1* 2^1000

11 = 1011(2)
1*x^8 + 0*x^4 + 1*x^2 + 1*x
x   ，      ->          (    2 )
*/
function Power(base, exponent)
{
    p = exponent;
    if(base==0) return 0;
    else if(p==0) return 1;
    else if(p<0)
        p = -p;//  
    var ans = 1;
    while(p) {
        // console.log(p);
        if(p&1) {
            ans *= base;
        }
        base*=base;//       
        p = p>>1;//          
    }
    return exponent>0?ans:1/ans;
}

console.log(Power(2, 3));

2.奇数が偶数より前になるように配列順序を調整する
時間制限:1秒空間制限:32768 K整数配列を入力し、すべての奇数が配列の前半に位置し、すべての偶数が配列の後半に位置し、奇数と奇数、偶数と偶数の相対的な位置が変わらないように関数を実現します.
この問題を見て、私はソートの思想を思い出しました.この問題はソートの変種です.ただ、ここでソートのルールを再制定しただけで、通常の降順や昇順ではありません.
2つの方向、時間は空間を変えて、空間は時間を変えます.
タイムスワップ
挿入思想とバブルソート思想を利用することができ,時間交換空間にも2つの方法がある.
1.元の配列上で操作して、順序付けの思想を挿入して、2つのポインタを制定して、iとj、iは前の掃面から第1の偶数を見つけて、jはi+1から第1の奇数をスキャンして見つけて、i......j-1は後ろに1つの位置を移動し、tmp=array[j]を事前に保存し、j位置のtmpをi位置に挿入し、交換を完了する.eg:1 2 4 6 7 i j->交換後1 7 2 4 6,jはi+1であるため,iがjを見つけなければ見つからない(iはlenに着く)という判断境界を利用する.

function reOrderArray(array)
{
    if(array.length==0) return [];
    var len = array.length;
    var i = 0;
    while(iwhile (i < len && judge_q(array[i])) i++;
        var j = i + 1;
        while (j < len && !judge_q(array[j])) j++;
        if (j < len) {
            var tmp = array[j];
            for (var k = j; k > i; k--) {
                array[k] = array[k - 1];
            }
            array[i] = tmp;
        }else {
            break;
        }
    }
    return array;
}

function judge_q(a) {
    if(a&1) return true;
    else return false;
}

var b = [1,2,4,6,7];
console.log(reOrderArray(b));

時間の複雑さO(N^2)はもちろん空間的にかなり節約できました.(サードパーティ配列なし)
2.上のことを理解すると、きっと泡で並べ替えたいと思ってしまう

//C++
for (int i = 0; i < array.size();i++)
{
    for (int j = array.size() - 1; j>i;j--)
    {
        if (array[j] % 2 == 1 && array[j - 1]%2 == 0) //      
        {
            swap(array[j], array[j-1]);
        }
    }
}

O(N^2)の複雑さでもあります
くうかんへんかんじかん
O(n)線形時間の複雑さ,空間的に1つの配列を多く開く.

function reOrderArray(array)
{
    var ans_q = [];
    var ans_o = [];
    for(var i = 0; i <array.length; i++) {
        if(array[i]&1) {
            ans_q.push(array[i]);
        }
        else {
            ans_o.push(array[i]);
        }
    }
    return ans_q.concat(ans_o);
}