[已解决]Python：每日一题 304

Croper

阴阳神万物主 发表于 2020-1-13 00:01
这样还有不对的吗，我这小脑瓜还是太嫩了

输入[2,1,5],预期结果是1对，输出2对。。

Croper

Croper 发表于 2020-1-13 00:03
输入[2,1,5],预期结果是1对，输出2对。。

你把这一段拿去自己试试呗：

from random import randint

def solve2(lst:'list of int',rep=False)->int:
    res = 0
    temp = sorted(lst) if rep else sorted(set(lst))
    for each in lst:
        if each in temp[1:]:
            res += temp.index(each)
            temp.remove(each)
    return res





def func304(l:list):
    l2=[]
    map={}
    for i in l:
        exist=False
        p,q=0,len(l2)
        while (p<q):
            n=(p+q)//2
            if (i==l2[n]):
                exist=True
                map[i]=n
                break
            if (l2[n]<i):
                q=n
            else:
                p=n+1
        if (not exist):
            l2.insert(p,i)
            map[i]=p
    ret=0
    for n in map.values():
        ret+=n
    return ret


      

for i in range(2000):
    l=[randint(1,10) for _ in range(randint(i//100+2,i//50+2))]
    ret1=solve2(l[:])
    ret2=func304(l[:])
    if (ret1!=ret2):
        print()
        print("error")
        print(l)
        print("your result=",ret1)
        print("my result=",ret2)
        break
    if (i//50==0):
        print(".",end="")
else:
    print("correct!")

阴阳神万物主

Croper 发表于 2020-1-13 00:09
你把这一段拿去自己试试呗：

我已经将能有的规律重新思考了一遍，无非就是 全升、全降、升降升、降升降，所以这个应当对(思考状)

def solve2(lst:'list of int',rep=True)->int:
    res = 0
    temp = sorted(lst) if rep else sorted(set(lst))
    for i in range(len(lst)):
        each = lst[i]
        if each in temp[1:]:
            res += temp.index(each)
            temp.remove(each)
        elif each in temp[:1]:
            if each not in lst[i+1:]:
                temp.remove(each)
    return res

Stubborn

阴阳神万物主 发表于 2020-1-13 00:23
我已经将能有的规律重新思考了一遍，无非就是 全升、全降、升降升、降升降，所以这个应当对(思考状)

考虑下并归

# -*- coding: utf-8 -*-
# !/usr/bin/python3
"""
@ version: ??
@ author: Alex
@ file: Algorithm
@datetime: 2020/1/13 - 0:53
@explain:
"""
import random
from functools import wraps
import time

def thisTime(func):
    @wraps(func)
    def wrapper(funcc, count):
        start = time.time()
        print(f"{count} This result-> {func(funcc(count))}")
        print(f"{count} This  time -> {start - time.time()}")
    return wrapper

def create_random(count):
    """Create random unordered data"""
    data = list(range(count))
    random.shuffle(data)
    return data

def create_reversed(count):
    """Create reversed data"""
    return list(range(count, 0, -1))

@thisTime
def func304(array:list):
    """归并"""
    def merge(arr, left, mid, right, res):
        """合并"""
        l,r,start = left, mid + 1, left
        Array = [0 for _ in range(len(arr))]
        while l <= mid and r <= right:
            if arr[l] < arr[r]:Array[start],l,start = arr[l],l+1 , start+1
            else:Array[start], r, start,res = arr[r], r+1, start +1, res + mid - l + 1
        while l <= mid:Array[start],l, start = arr[l], l+1, start+1
        while r <= right:Array[start], r, start = arr[r], r+1, start+1
        for i in range(left, right + 1):arr[i] = Array[i]
        return res

    def sort(arr, left, right, res):
        if left >= right: return res   # 出口
        mid = (left + right) >> 1
        # 分
        l = sort(arr, left, mid, res)
        r = sort(arr, mid+1, right, res)
        # 并
        return merge(arr, left, mid, right, l + r)

    return sort(array, 0, len(array)-1, 0)


func304(create_random, 1000)
func304(create_reversed, 1000)
func304(create_random, 5000)
func304(create_reversed, 5000)

Unicorn#

来了
尝试归并

# -*- coding: utf-8 -*-
def solve(nums):
    count = 0
    def f(i, j):
        if i == j or i == j-1:
            return
        nonlocal count, nums
        sep = (i + j)//2
        f(i, sep)
        f(sep, j)
        temp = []
        x = i
        y = sep
        while x < sep and y < j:
            if nums[x] > nums[y]:
                temp.append(nums[x])
                count += 1
                x += 1
            else:
                temp.append(nums[y])
                y += 1
        for t in range(x, sep):
            temp.append(nums[t])
        for t in range(y, j):
            temp.append(nums[t])
        nums[i:j] = temp
    f(0, len(nums))
    return count

Unicorn#

Stubborn 发表于 2020-1-13 00:37
考虑下并归

巧了，我第一反应也是归并
(毕竟这是归并的例题)

kinkon

这样会超时吗？

def fun304(n):
    c, res = 0, []
    while len(n) > 1:
        res = n.pop(0)
        for i in n:
            if res > i: 
                c += 1
    return c
if __name__ == '__main__':
    print('示例1 输出：',fun304([2,4,1,3,5]))
    print('示例2 输出：',fun304([1,2,3,4]))

TJBEST

我这次一反常态，来了一个较短的代码，速度貌似还不慢

def fun304(arr):
    if len(arr)< 2:
        return 0
    sortedList = sorted(arr)
    result = 0
    for each in arr:
        index = sortedList.index(each)
        result = result + index
        del sortedList[index]
    return result

fan1993423

阴阳神万物主 发表于 2020-1-13 00:23
我已经将能有的规律重新思考了一遍，无非就是 全升、全降、升降升、降升降，所以这个应当对(思考状)

我要求不重复的序列对哦,[5,1,1,5,1]结果应该是1

cxzmgs

厉害啊

kinkon

用迭代速度还可以吧

from itertools import combinations as c
def p304(n):
    res, ct = [], 0    
    res.extend(list(c(n, 2)))
    for i in res:        
        if i[0] > i[1]: ct += 1
    return ct

kinkon

TJBEST 发表于 2020-1-13 10:57
我这次一反常态，来了一个较短的代码，速度貌似还不慢

向前辈学习，速度真不错

阴阳神万物主

fan1993423 发表于 2020-1-13 12:57
我要求不重复的序列对哦,[5,1,1,5,1]结果应该是1

哦，那层楼没说，要把rep参数设置为False，我补充一下说明

def solve2(lst:'list of int',rep=True)->int:
    '''
    该函数的功能是：
        统计并返回待查询列表中的逆序对总数
    必要参数：
        lst 为 待查询列表。
    可选参数：
        rep 是一个布尔值，为是否需要统计重复的逆序对。
            为真，则统计重复的；
            为假，则不统计，
            默认值为真。
    '''
    res = 0
    temp = sorted(lst) if rep else sorted(set(lst))
    for i in range(len(lst)):
        each = lst[i]
        if each in temp[1:]:
            res += temp.index(each)
            temp.remove(each)
        elif each in temp[:1]:
            if each not in lst[i+1:]:
                temp.remove(each)
    return res

阴阳神万物主

Stubborn 发表于 2020-1-13 00:37
考虑下并归

但是，归并的话，如何剔除重复的逆序对呢？记忆化搜索吗？

Stubborn

阴阳神万物主 发表于 2020-1-13 17:47
但是，归并的话，如何剔除重复的逆序对呢？记忆化搜索吗？

题目有说要去重吗

阴阳神万物主

Stubborn 发表于 2020-1-13 18:13
题目有说要去重吗

但我那一楼是在回复别人提的去重的拓展32楼
我对于本题的解法最后是在26楼

记忆的欠片

def counter(arry):
    count = 0
    for i in arry:
        for j in arry[arry.index(i):]:
            if j < i:
                count += 1
    return count

776667

def fun304(x):
    count = 0
    for i in range(len(x)-1):
        for j in range(len(x))[i+1:]:
            if x[i] > x[j]:
                count += 1
    return count

zltzlt

阴阳神万物主 发表于 2020-1-12 23:37
看了看别人的出错数据，感觉这回稳

还是会超时，原因在于 temp.index(each)

zltzlt

阴阳神万物主 发表于 2020-1-13 00:23
我已经将能有的规律重新思考了一遍，无非就是 全升、全降、升降升、降升降，所以这个应当对(思考状)

超时