[Algorithm Champions] Week 4, No.6

19067 ワード
アルゴリズム#アルゴリズム# テキストリンク

質問する



に答える


これは
  • orderの文字順に配列を並べ替える問題です.

    • 海図の使用


  • 空間的複雑度がO(1)であるため,海図を用いた.
    ->arrayはorderの数字のみで構成されるため、orderの文字数ごとに何文字あるかを計算してハッシュマッピングに入れると、arrayが長くなってもハッシュマッピングには3対しか存在しないのでO(1)となる.

  • まずorderの各要素がarrayにどれだけ含まれているかを計算し、ハッシュマッピングに格納します.

  • 置いた後、orderの要素が海図にあるかどうかを確認します.
    ->含まれている場合は、その数で配列に値を入れます.
    ->ない場合は、orderの次の要素に移動して実行します.

  • 最後に、並べ替えられた配列を返します.

    • ポインタの操作


  • これは新しい余分な空間を使わずに解放する方法です.

  • 左、中、右のポインタを作成します.

  • 中間ポインタが右ポインタ以下である場合
  • 現在値(curVal)を、中間ポインタが指す値に設定します.
  • の現在の値が最初の数値である場合(order[0])、左ポインタが指す数値と現在の値を置き換えます.次に、左ポインタと中間ポインタを追加します.
  • の現在の値が2番目の数字(order[1])である場合、中間ポインタは1つだけ増加します.
  • の現在の値が3番目の数字(order[2])である場合、現在の値と右ポインタが指す値を変更し、右ポインタを1つ減らします.

  • 最後に、再配置された配列を返します.

    • コード#コード#


    海図の使用

    package com.company.w4;

import java.util.Arrays;
import java.util.HashMap;

/*
date: 21.07.08

input: 정수 배열, 세 숫자가 들어간 배열
output: 정수 배열
constraints:
    첫 번재 배열은
        두 번째 배열에 있는 정수만 포함한다.
        두 번째 배열에 있는 정수 세개가 모두 포함될 수도 있고 안될 수도 있다.
    두 번째 배열은 서로 다른 세 숫자만 들어간다.
    있는 배열에서 순서를 정렬해야한다. 새로운 공간 사용 불가.
    원하는 순서는 오름차순이나 내림차순일 필요가 없다.
edge cases:
    {2}, {1,3,2} => {2}
    {2,1}, {1,3,2} => {1,2}
    {2,1,3}, {1,3,2} => {1,3,2}

 */
public class No6_2 {
    public static void main(String[] args) {
        int[] array = {1, 0, 0, -1, -1, 0, 1, 1};
        int[] order = {0, 1, -1};
        System.out.println(Arrays.toString(desiredOrder(array, order)));
    }

    public static int[] desiredOrder(int[] array, int[] order) {
        // base case
        if (array.length == 1) return array;

        HashMap<Integer, Integer> map = new HashMap<>();
        for (Integer n : array) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        int idx = 0;

        for (int i = 0; i < order.length; i++) {
            if (map.containsKey(order[i])) {
                for (int j = 0; j < map.get(order[i]); j++) {
                    array[idx++] = order[i];
                }
            } else
                continue;
        }

        return array;
    }
}

    ポインタの操作

    package com.company.w4;

import java.util.Arrays;

/*
date: 21.07.08

input: 정수 배열, 세 숫자가 들어간 배열
output: 정수 배열
constraints:
    첫 번재 배열은
        두 번째 배열에 있는 정수만 포함한다.
        두 번째 배열에 있는 정수 세개가 모두 포함될 수도 있고 안될 수도 있다.
    두 번째 배열은 서로 다른 세 숫자만 들어간다.
    있는 배열에서 순서를 정렬해야한다. 새로운 공간 사용 불가.
    원하는 순서는 오름차순이나 내림차순일 필요가 없다.
edge cases:
    {2}, {1,3,2} => {2}
    {2,1}, {1,3,2} => {1,2}
    {2,1,3}, {1,3,2} => {1,3,2}

포인터 세 개 사용하기


 */
public class No6_3 {
    public static void main(String[] args) {
        int[] array = {1, 0, 0, -1, -1, 0, 1, 1};
        int[] order = {0, 1, -1};
        System.out.println(Arrays.toString(desiredOrder(array, order)));
    }

    public static int[] desiredOrder(int[] array, int[] order) {
        System.out.println(Arrays.toString(array));
        int leftP = 0, midP = 0, rightP = array.length - 1;

        while (midP <= rightP) {
            int curVal = array[midP];

            if (curVal == order[0]) {
                array[midP] = array[leftP];
                array[leftP] = order[0];
                leftP++;
                midP++;
            } else if (curVal == order[1]) {
                midP++;
            } else if (curVal == order[2]) {
                array[midP] = array[rightP];
                array[rightP] = order[2];
                rightP--;
            }
        }

        return array;
    }
}
    Centosオンラインyum構成
    [TIL#21]for Moon