67847

[code]

    li = ['1','2','3','4','5']
    
[/code]

これの文字列を  
1,2,3をAに、4,5をBに効率よく置き換える方法はありますか？

補足  
リストの右側 - リストの左側 = 3になった時に  
リストの左側をA, リストの右側をBにしたいです。  
これらは、連続してなければいけません。

[code]

    left = 0
    total = sum(li)
    for i in li:
        left += i
        if total - left == 3:
            ??????
    
[/code]

という感じで？？？で詰まっています。


CC BY-SA 4.0
2020-06-20T06:58:04.563
67827
2020-06-21T06:24:16.480
2020-06-20T07:32:52.487
36091
36091
question
python python3
リストのなかみを効率よく置き換えるには？


> リストの右側 - リストの左側 = 3になった時に

「(リストの右側の合計) - (リストの左側の合計) = 3になった時に」ですね。  
以下のコードで実現できると思います。

[code]

    li = ['1','2','3','4','5']
    lin = [int(x) for x in li] #数値のリストに変換
    n = 3
    len_li = len(li)
    for i in range(len_li):
        if sum(lin[i:]) - sum(lin[0:i]) == n:
            result = ['a'] * i + ['b'] * (len_li-i)
            break
    else:
        result = ""
    
[/code]

このコードは3に一致しなかったとき空文字列を結果としています。

* * *

上の例では左右の部分リストの合計を毎回最初から計算していますので、以下のコードの方が計算の量は少ないです。

[code]

    li = ['1','2','3','4','5']
    lin = [int(x) for x in li] #数値のリストに変換
    n = 3
    len_li = len(li)
    sum_left = 0
    sum_right = sum(lin)
    for i in range(len_li):
        if sum_right - sum_left == n:
            result = ['a'] * i + ['b'] * (len_li-i)
            break
        sum_left += lin[i]    
        sum_right -= lin[i]    
    else:
        result = ""
    
[/code]


CC BY-SA 4.0
2020-06-20T08:54:17.733
67829
2020-06-21T06:24:16.480
2020-06-21T06:24:16.480
35558
35558
67827
answer


下は時間計算量と空間計算量はともにO(n)です。差が3になる区切りが存在しない場合は、配列を変更しないとしています。

[code]

    li = ['1','2','3','4','5']
    total = sum(int(n) for n in li)
    if total >= 3 and total % 2 != 0:
        half3 = (total - 3) // 2
        part_total = 0
        for idx, n in enumerate(li):
            if part_total == half3:
                li[:] = ['A'] * idx + ['B'] * (len(li) - idx)
                break
            elif part_total > half3:
                break
            part_total += int(n)
    
    print(li)
    
[/code]

途中で長さ`len(li)`の配列を作ってしまっているので、これをなくせば空間計算量をO(1)にすることもできます。ただし、ちょうど3になるかを判定するための部分が必要になります。少し妥協して、下は、差が
**3以下** になるところで区切りを入れています。(ちょっとあやしい)

[code]

    li = ['1','2','3','4','5']
    total = sum(int(n) for n in li)
    half3 = (total - 3) / 2
    part_total = 0
    for idx, n in enumerate(li):
        if part_total < half3:
            li[idx] = 'A'
        else:
            li[idx] = 'B'
        part_total += int(n)
    
    print(li)
    
[/code]

なお、計算量が少ない＝高速・低メモリではないことに注意してください。与えられた配列の大きさに応じてどれぐらいの時間やメモリが消費するのかの目安にしか過ぎません。与えられる配列が小さい、または、一定の大きさ以下である場合は、逆に遅かったりメモリ消費が大きかったりしますのでご注意ください。


CC BY-SA 4.0
2020-06-20T22:51:27.603
67847
2020-06-20T22:51:27.603
7347
67827
answer