C言語の配列の並び替えでTime Limit Exceededというエラーが出ます。

Question

numsという配列を並び替える問題で、LeetCode内でTime Limit Exceededというエラーが出ます。

LeetCodeの問題です。

nums配列は、このようになっています。[0,0,1,1,1,2,2,3,3,4]

このnumsを重複がないように並び替えて、余った要素には、''を代入します。
並び替えた後のnums配列は、[0,1,2,3,4,,,,,]です。

そしてプログラムは、重複のない数字の数である5を返します。

Time Limit Exceededというエラーを解決するためにどのように修正すればいいでしょうか？

//修正前

int removeDuplicates(int* nums, int numsSize){
    
    
    int i;
    int j;
    int num;
    num=numsSize;
    

	for (i = 0;i < numsSize;i++) {
        if(i!=0){
            if(nums[i-1]==nums[i]){
                num--;//重複があった分をマイナスする。ユニークな数値の数にする
        
                for(j=i; j<numsSize-1;j++){//重複が確認されたので、全ての要素を左に詰めるためのfor loop
                    nums[j]=nums[j+1];

                    if(numsSize-1==j+1){
                        nums[j+1]='_';//要素の最後には'_'を代入
                    }
                }
                //重複があった場合は、左に詰めるから詰めた分を再度重複がないか確認するために、-1する。
                i--;
            } 
        }
    }
    return num;
}

//修正後

int removeDuplicates(int* nums, int numsSize){

    int i;
    int num=0;

　//ここでえらーが出ます。このコードは input[1,1] や、input[1]に対応するためのコードです。
   if(nums[0]==nums[numsSize-1]){
       num++;
   }
 
	for (i = 1;i < numsSize;i++) {
        
        
        if(nums[i-1]!=nums[i]){
        
        
            if(i==numsSize-1){
                nums[num]=nums[i-1];
                num++;
                
                nums[num]=nums[i];
                num++;
        
            }else{
                nums[num]=nums[i-1];
                num++;
            }
        }
    }
   
    
    return num;
}

=================================================================
==30==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001b0 at pc 0x55a3fe08f25d bp 0x7fff6f41e710 sp 0x7fff6f41e700
READ of size 4 at 0x6020000001b0 thread T0
    #2 0x7f29855c20b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x6020000001b1 is located 0 bytes to the right of 1-byte region [0x6020000001b0,0x6020000001b1)
allocated by thread T0 here:
    #0 0x7f2986207bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #3 0x7f29855c20b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa 00 04 fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8010: fa fa 00 fa fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8020: fa fa fd fa fa fa fd fa fa fa fd fa fa fa 00 00
=>0x0c047fff8030: fa fa fd fa fa fa[01]fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==30==ABORTING

Comments

[fana]

> Time Limit Exceededというエラーが出ます

何の話ですか？　それは「エラー」なのですか？
どこぞのサイトで時間制限がある問題に取り組んでいて「そのコードだと遅ぇよ」って言われただけの話ではないのでしょうか？

[dodox86]

競技プログラミング系のことをやっていて、プログラム実行の制限時間越えのことを言われているのでしょうか。（＜C言語であれば数秒以内に完了とか）　その場合、提示のコードでのやり方に問題があって、入力データによってはその時間内に完了できないのだと思われます。その問題のあるサイトのURL等を明示しましょう。

[alizona]

https://leetcode.com/problems/remove-duplicates-from-sorted-array/
です。

[dodox86]

この欄にではなく、質問に加筆、修正するかたちで示してください。他の方々も閲覧するものです。

[dodox86]

で、そのエラーの解決方法自体が課題なのだと思います。課題条件を満たせるよう充分に速いロジックを組むという。

[episteme]

ソコの問題には "余った要素には、'_'を代入"なんて書いてないぞ。

[dodox86]

成り行きをみるに、ご自身ではデバッガーなどを使って実行させていないとみましたが、どうでしょう。

[alizona]

It does not matter what you leave beyond the returned k (hence they are underscores).

[Zuishin]

いやだから、_ を入れず放置していいってことでしょ。そもそも配列は int サイズで _ は char サイズだし。

[alizona]

放置したら、もともとの数値残りませんか？

[Zuishin]

It does not matter.

> It does not matter what you leave beyond the returned k
(訳) k 以降の要素に何を残しても構いません

[dodox86]

課題文中には
> It does not matter what you leave beyond the first k elements.

としか書いていなく、Exampleの方で (hence they are underscores) が追加されているので、
「kを超えて放置された要素は問わない。だから例として'_'で埋めとくよ。（意訳）」程度の意味ではないでしょうか。必須条件ではない。

[alizona]

it does not matter whether underscore or something elseって意味かと思ってました。

[dodox86]

（かぶった上の劣化意訳）

[dodox86]

必須ではないけど、反対に言えば入れても良い。入れたところで適切なロジックでプログラムを書けばパスするはずです。問題には「O(1)で」とあるので。

[jimbe]

「並び替え」では無くて「詰める」だけなんですね。

Answer 1

アルゴリズムは皆さまと同じ考えと思いますので、コードだけ。

int removeDuplicates(int* nums, int numsSize){
    if(nums == NULL || numsSize <= 0) return 0; //param check
    int c = 0;
    for(int i=1; i<numsSize; i++) {
      if(nums[c] != nums[i]) nums[++c] = nums[i];
    }
    return c+1;
}

Comments

[alizona]

ありがとうございました。やっとスッキリしましたw

Answer 2

Time Limit Exceeded どころか、いつになったら終わるのか？無限ループしてるんじゃないか？と思ったので、デバッグコードを埋め込んで i, num の値と配列 nums[] の内容を表示してみました。

void pArr(int a[], int asize) // 配列の内容を表示する
{
    for (int i = 0; i < asize; i++) {
        if (a[i] >= 0 && a[i] <= 9)
            printf("%d ", a[i]);
        else
            printf("_ ");
    }
    printf("\n");
}

int removeDuplicates(int* nums, int numsSize)
{
    int num, i, j;

    num = numsSize;
    for (i = 0; i < numsSize; i++) {
        printf("i = %d, num = %2d: ", i, num);  // 追加 for DEBUG
        pArr(nums, numsSize);                   // 追加 for DEBUG

        if (i != 0) {
            if (nums[i - 1] == nums[i]) {
                num--; // 重複があった分をマイナスする。ユニークな…

実行結果です。

i = 0, num = 10: 0 0 1 1 1 2 2 3 3 4
i = 1, num = 10: 0 0 1 1 1 2 2 3 3 4
i = 1, num =  9: 0 1 1 1 2 2 3 3 4 _
i = 2, num =  9: 0 1 1 1 2 2 3 3 4 _
i = 2, num =  8: 0 1 1 2 2 3 3 4 _ _
i = 2, num =  7: 0 1 2 2 3 3 4 _ _ _
i = 3, num =  7: 0 1 2 2 3 3 4 _ _ _
i = 3, num =  6: 0 1 2 3 3 4 _ _ _ _
i = 4, num =  6: 0 1 2 3 3 4 _ _ _ _
i = 4, num =  5: 0 1 2 3 4 _ _ _ _ _
i = 5, num =  5: 0 1 2 3 4 _ _ _ _ _
i = 6, num =  5: 0 1 2 3 4 _ _ _ _ _
i = 6, num =  4: 0 1 2 3 4 _ _ _ _ _
i = 6, num =  3: 0 1 2 3 4 _ _ _ _ _
i = 6, num =  2: 0 1 2 3 4 _ _ _ _ _
i = 6, num =  1: 0 1 2 3 4 _ _ _ _ _
i = 6, num =  0: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -1: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -2: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -3: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -4: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -5: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -6: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -7: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -8: 0 1 2 3 4 _ _ _ _ _
i = 6, num = -9: 0 1 2 3 4 _ _ _ _ _
（以下、延々と続きます）

これ、nums[5] ～ nums[9] に '_' が書き込まれた後も
if (nums[i - 1] == nums[i]) 条件は成立し続けるので無限ループしてるようですね。
デバッガ使うのが筋でしょうが、こんな風に簡単なデバッグコードを埋め込む（いわゆるprintfデバッグ）だけでも調査はできますよ。

Comments

[alizona]

ありがとうございました。

Answer 3

"左に詰める"に時間食ってるんでしょうか。
だったらそんな処理やんなきゃいい。

#include <stdio.h>

// 空いた位置に'_'を埋めてはいない(その必要はないから)

int removeDuplicates(int* nums, int numsSize) {

    int read_inx;      // 読む位置
    int write_inx = 0; // 書く位置
    int last_value ;   // 最後に書いた値

    for ( read_inx = 0; read_inx < numsSize; ++read_inx ) {
        // 最初の一回、もしくは"最後に書いた値"と"今読んでる値"が異なるなら
        // "今読んでる値" を 書く("最後に書いた値"も更新)
        if ( read_inx ==0 || last_value != nums[read_inx] ) {
            nums[write_inx++] = last_value = nums[read_inx];
        }
    }
    return write_inx; // 重複を取り除いた後の要素数
}

int main() {
  int nums[10] = { 0,0,1,1,1,2,2,3,3,4 };
  int numsSize = 10;
  
  numsSize = removeDuplicates(nums, numsSize);

  for ( int i = 0; i < numsSize; ++i ) {
    printf("%d ", nums[i]);
  }
  return 0;
}

Comments

[alizona]

ありがとうございます。アドバイスいただいたコードを理解できました。また正常に動作しました。
今、lastValueを使わない方法も探してます。

[episteme]

なくてもできる(できた)。なんてことないっしょ。

[alizona]

わかりました。ありがとうございました。

Answer 4

ここまで書けているので、ある程度ご理解されている前提でお話します。

・要求されている答えが要素数 num だけなのであれば、
num = 1 としておいて、配列を前から順に読んでいき、
「値が変化するところ」　0->1 とか 1->2 とかで num をインクリメントするだけでよいと思います。

次に、

・配列 nums も要素数 num も両方求められている場合、
重複のたびに配列を詰めていたのでは、時間がかかってしまうので、
読み込み用のインデクス src_i = 1 、書き込み用のインデクス dst_i = 0
として、読み込み用インデクス src_i で forを回して 配列を前から順に読んでいき、
「前の値」(nums[src_i-1])と「今の値」(nums[src_i])を比較します。　
もし値が変化していたら、「前の値」を nums[dst_i] に格納し、dst_i をインクリメントします。
dst_i が src_i に追いつく(dst_i >= src_i)ことはない、
ということを利用します。
要は、詰める、のではなく、配列を読みながら、同じ配列内に値が重複しないように
答えの配列を作っていくイメージです。

さっぱり、わからなかったらご質問ください。

Comments

[alizona]

ありがとうございます。アドバイスいただいた通りにコードが書けているでしょうか？
Runtime Errorが原因はわかっていません。エラーと、コードを質問分に追記しました。

[ak.n]

いえ、色々間違っています。
まず、 最初の num = 0 です。最初の値の格納先になります。
次に、for (i=0 ですが i=1 からスタートすれば if (i!=0)は不要ですね、for のなかで、何度もチェックするような処理はできるだけ減らした方がいいです。
それから、nums[num]=nums[i]; は nums[num]=nums[i-1];
ですね。
あとは、最後に配列の末尾まで、'_' で埋める処理は、お任せします。

[ak.n]

ん－んとですね、まず、何を自分がやろうとしているかを、よく理解して頂きたいと思います。
配列のインデクスは０から始まりますね、0番から10番までのマスの絵を書いて、そこに数字を並べてみて、
どういう処理をしようとしているか、よーーく考えてから、書いてくださいね。

[alizona]

"それから、nums[num]=nums[i]; は nums[num]=nums[i-1];"
ということが理解できなかったのですが、自分のコードを実行したところoutputの値は正解です。
ただ、Runtime Errorなのですが、それとは関係はないですよね？

[alizona]

質問欄の修正後コードの中の if(nums[0]==nums[numsSize-1]){
num++;
}でエラーが出るのですがアドバイスいただけないですか？

[alizona]

input [1,1] の時にoutput [ ]にならないようにするためのコードです。
また、input[1]の時に、[ ] にならないようにするためです。

[jimbe]

横から失礼します。
numsSize が 0 (input が [] ) の場合に nums[numsSize-1] は領域外を指してしまいますよ。

Answer 5

とりあえず，「そのコードだと遅ぇよ」って話であれば，

//重複が確認されたので、全ての要素を左に詰める

という処理が最も重いであろう（というか，それくらいしか処理が無い）から，
この処理を実施する回数をなるべく減らすことを考えてみては．

例えば，

1,1,1,1,2,3,....

っていう具合に1が重複しているとして，
「左に１個分詰める」処理を３回も実施せずとも「左に３個分詰める」処理を１回やればいいよね，的な話は誰でも思いつくでしょう．
まずはそのくらいのことをやってみてはどうでしょうか．

Comments

[alizona]

やってみます。ありがとうございます。

[fana]

それでも「遅い」と言われるなら（←多分，言われるものと予想），そもそも「いちいち詰めない」ことを考えればよいかと．

[alizona]

nums[i-1]とnums[i]を比較して、値が違うときだけ代入する方法にしました。

Answer 6

google翻訳
制限時間を超えました

これはC言語上でのエラーではなく、実行環境でのエラーじゃないでしょうか
ってことですんで、どういう環境で実行させてるんでしょうか。
なにかの課題ってことでしょうか

Comments

[alizona]

返信ありがとうございます。leetcodeです。