search
LoginSignup
0
Help us understand the problem. What are the problem?

posted at

Codility lesson3 PermMissingElem

Lesson3のPermMissingElemは欠けている数字を当てるというものです。
長さNのリストには1~N+1のいずれかが異なる形で入っている、逆にいうと一つ欠けていることがわかります。
[1,2,4,5]は3ですね。
[1,2,3,4]は5ですね。

さて今回の問題を考える上で、配列の順番を変えても特に問題はありませんよね。
例えば
[3,1,2,4]を[1,2,3,4]にする
[4,5,1,2]を[1,2,4,5]にした方が処理しやすいですよね。
なので今回は前回のlesson2 OddOccurencesInArrayのとき同様に先にソートしてから処理していきます。

アルゴリズムは以下の通りです。
1.順番通りにソートする
2.インデックス番号と比較してインデックス番号に対応している数字が来ていれば次に進む。
3.2の処理を繰り返し行うことでインデックス番号と対応していない数字、つまり欠けている数字の場所に到達するまで行う

コードは以下の通り

def solution(A):
    A = sorted(A)
    i = 0
    len_A = len(A)
    while  i+1 == A[i]:
        if i < len_A -1:
            i +=1
        elif i == len_A -1:
            i +=1
            break
    return i+1

さて結果は。。。。?

スクリーンショット 2022-06-12 3.02.19.png

あれ90%...?
どうやら空のリストを受け取った時の処理を書いていなかったためにエラーが生じてしまっているようです。
ただ空のリストの時何を返せばいいんでしょうか。。。?

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
0
Help us understand the problem. What are the problem?