0

与えられた数字を二次元で保存したいです。例えば、数列{3,12,4,1,5,8}を与えられたとして、一番目の数字3を配列1に挿入、二番目の数字12は、3より大きいので別の配列2に挿入、左から走査し、4は12より小さいので配列2に挿入、1は左から走査し3より小さいので配列1に挿入...ということを行いたいです。
構造的には、二次元リスト

int s = {3,12,4,1,5,8}
int array[N][N]; //Nは入力される文字数
array[0][0] = s[1];
int j = 1;
for (int i=1; i<N; i++){
    if (s[i] < array[i-1][i-1]{
        array[i][i] = array[i-1][i-1];
        array[i-1][i-1] = s[i];
    }
    else {
        if array[i][i+j] > s[i];
        array[i][i+j] = s[i];
}

というような構造を考えていたのですが、これだとその数字が二番目の配列より大きかったときに対処できませんし、だからといってforループを再び使うと計算量が莫大になってしまいます。また、配列なので既存の要素の上に挿入といったことも手間がかかります…
二次元配列を使うべきではないのでしょうか…?お力を貸していただけると嬉しいです。

追記
質問文修正しました。
期待される出力は

head-1-3
head-4-12
head-5
head-8

といった感じです
イメージ的にはこの画像のような感じにしたいのですが、うまく説明できなくて申し訳ありません…
期待される動作

6
  • 今の例にひとつ要素を追加して S = {3, 12, 4, 1, 5, 8} とした場合、出力は {{1, 3}, {3, 4, 12}, {5}, {8}} というような感じになる、という理解であっていますでしょうか。
    – nekketsuuu
    Commented 2020年4月12日 15:50
  • 回答はC言語限定、速度優先ですか?与えられた数字は重複なしですか?保存した結果の用途が想像つきません、よろしければ何に使うか教えて欲しいです。 Commented 2020年4月12日 23:28
  • @nekketsuuu はい、そのとおりです
    – Avril
    Commented 2020年4月13日 3:00
  • @akiraejiri C言語、速度優先(目標はO(nlogn)です。与えられた数字は重複がある可能性があります。こちらはデータ構造とアルゴリズムの問題で、最終的なゴールはこれらのリストを一つのリストにまとめることです。しかしまとめる前に、上記したしたようなプロセスを踏まなければなりません。
    – Avril
    Commented 2020年4月13日 3:05
  • {3, 12, 4, 1, 5, 8} に2を追加した場合、{4,12}が{2,4,12}になると思いますが、{2,12,4}ではだめなのですね?memcpy等のライブラリ使用は可ですか? Commented 2020年4月13日 3:22

1 件の回答 1

0

回答

 2次元配列を使ったコードの例です。
 配列の途中に要素を挿入していません。

機能

 コードを書けば、「何のための処理か」を理解できるかと思いましたが、未だよくわかっていません。
 質問された方の意図どおりの動作であるか自信がありません。
 性能重視とのことでしたので、処理の途中では配列の要素を入れ替えず、最後に昇順になるよう並べ替えています。

処理内容

  1. 行先頭列が未設定(0)の場合
    無条件に入力データを先頭列に設定する。
  2. 入力データが先頭列より小さい場合
    入力データを先頭列へ、旧先頭列を末尾に設定する。
  3. 1.、2.に該当しない場合
    次の行に対して、1.または2.を行う。
  4. 処理の終了時
    各行の第2列から最終列のデータを反転する。
    ※第2列から最終列のデータは降順のため昇順に並び替えています。

ソース

  • 入力データs
    {3, 12, 4, 1, 5, 11, 2, 10, 9, 8, 4}
    としています。
  • デバッグ用に途中経過を表示しています。
#include <stdio.h>
#define NUM(A) (sizeof(A) / sizeof(A[0]))
#define N NUM(s)                                // Nは入力値の個数
int s[] = {3, 12, 4, 1, 5, 11, 2, 10, 9, 8, 4}; //入力データ
int array[N][N] = {0};
int a_num[N] = {0};
void print_result(int num);
void debug_print_input(int s[], int num);

int main(int argc, char *argv[]) {
  int is; // index of s
  int tmp;
  int row_num;
  debug_print_input(s, N);
  for (is = 0; is < N; is++) { //入力データ
    printf("%s\n", "-----------------------------------------");
    debug_print_input(s, is + 1);
    for (int i = 0; i < N; i++) { //行
      if (array[i][0] == 0) {     //先頭列が未設定
        /*入力データを無条件に先頭列に設定 */
        array[i][0] = s[is];
        a_num[i] += 1;
        row_num = i + 1;
        break;
      } else if (s[is] < array[i][0]) { //入力データが先頭列より小さい
        /* 入力データを先頭列へ、旧先頭列を末尾に設定 */
        tmp = array[i][0];
        array[i][0] = s[is];
        array[i][a_num[i]] = tmp;
        a_num[i] += 1;
        break;
      }
    }
    print_result(row_num);
  }
  //各行の2番目以降の列を反転
  for (int i = 0; i < row_num; i++) {
    for (int j = 1; j < (a_num[i] + 1) / 2; j++) {
      tmp = array[i][j];
      array[i][j] = array[i][a_num[i] - 1];
      array[i][a_num[i] - 1] = tmp;
    }
  }
  printf("%s\n", "=========================================");
  printf("最終結果\n");
  print_result(is);
  return 0;
}
void print_result(int num) {
  for (int i = 0; i < num; i++) {
    if (array[i][0] == 0)
      break;
    printf("%2d:", i);
    for (int j = 0; j < num; j++) {
      if (array[i][j] == 0)
        break;
      printf("(%2d) ", array[i][j]);
    }
    printf("\n");
  }
}
void debug_print_input(int s[], int num) {
  printf("s=");
  char *dlmt = "{";
  for (int is = 0; is < num; is++) {
    printf("%s%d", dlmt, s[is]);
    dlmt = ",";
  }
  printf("}\n");
}

実行結果

s={3,12,4,1,5,11,2,10,9,8,4}
-----------------------------------------
s={3}
 0:( 3)
-----------------------------------------
s={3,12}
 0:( 3)
 1:(12)
-----------------------------------------
s={3,12,4}
 0:( 3)
 1:( 4) (12)
-----------------------------------------
s={3,12,4,1}
 0:( 1) ( 3)
 1:( 4) (12)
-----------------------------------------
s={3,12,4,1,5}
 0:( 1) ( 3)
 1:( 4) (12)
 2:( 5)
-----------------------------------------
s={3,12,4,1,5,11}
 0:( 1) ( 3)
 1:( 4) (12)
 2:( 5)
 3:(11)
-----------------------------------------
s={3,12,4,1,5,11,2}
 0:( 1) ( 3)
 1:( 2) (12) ( 4)
 2:( 5)
 3:(11)
-----------------------------------------
s={3,12,4,1,5,11,2,10}
 0:( 1) ( 3)
 1:( 2) (12) ( 4)
 2:( 5)
 3:(10) (11)
-----------------------------------------
s={3,12,4,1,5,11,2,10,9}
 0:( 1) ( 3)
 1:( 2) (12) ( 4)
 2:( 5)
 3:( 9) (11) (10)
-----------------------------------------
s={3,12,4,1,5,11,2,10,9,8}
 0:( 1) ( 3)
 1:( 2) (12) ( 4)
 2:( 5)
 3:( 8) (11) (10) ( 9)
-----------------------------------------
s={3,12,4,1,5,11,2,10,9,8,4}
 0:( 1) ( 3)
 1:( 2) (12) ( 4)
 2:( 4) ( 5)
 3:( 8) (11) (10) ( 9)
=========================================
最終結果
 0:( 1) ( 3)
 1:( 2) ( 4) (12)
 2:( 4) ( 5)
 3:( 8) ( 9) (10) (11)
1
  • 丁寧な回答ありがとうございます。こちらは問題なのですが、私も正直100%理解できていません。やはり、二次元配列を使う場合は最後に昇順に並び替えるのが一番効率が良いのですね。Min-heapifyも考えましたが、多次元配列の場合もっと複雑になってしまいますかね
    – Avril
    Commented 2020年4月14日 9:07

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。