首页 > 求问英特尔9.2日笔试第3道题
头像
Google轰炸机
编辑于 2021-09-03 22:49
+ 关注

求问英特尔9.2日笔试第3道题

求问英特尔9.2日笔试第3道题:判断是否可以通过,移动数组某一连续部分,使得数组有序(下文称一步排序)
样例:
a = [3, 4, 4, 5, -2, -1]  # True
b = [1, 3, 5, 2, 4, 6]  # False
提前感谢!

经过两天的思索,自己想出了一个办法,用逆序对来确定能否一步排序。

def reversePairs(nums: List[Tuple[int]]):
    # 统计并记录逆序对,leetcode有原题
    def merge_sort(l, r):
        # 终止条件
        if l >= r: return 0
        # 递归划分
        m = (l + r) // 2
        res = merge_sort(l, m) + merge_sort(m + 1, r)
        # 合并阶段
        i, j = l, m + 1
        tmp[l:r + 1] = nums[l:r + 1]
        for k in range(l, r + 1):
            if i == m + 1:
                nums[k] = tmp[j]
                j += 1
            elif j == r + 1 or tmp[i][0] <= tmp[j][0]:
                nums[k] = tmp[i]
                i += 1
            else:
                for p in range(i, m + 1):
                    reverse_pairs[tmp[p]].append(tmp[j])
                nums[k] = tmp[j]
                j += 1
                res += m - i + 1  # 统计逆序对
        return res

    from collections import defaultdict
    reverse_pairs = defaultdict(list)
    tmp = [tuple()] * len(nums)
    merge_sort(0, len(nums) - 1)
    return reverse_pairs


def can_sort_by_one_move(nums):
    # 使用<逆序数对>来确定能否一步排序
    # 判据:设数组的逆序数对如下:[(xi, xj)], i,j=1,...,N. 称xi为逆序头,xj为逆序尾,并把逆序对看作是父子关系。
    # 则对每一个逆序头xi,若其孩子和其他逆序头一样,则说明可以一步排序
    # 例:nums = [3,4,1,2] 逆序对:[(3,1),(3,2),(4,1),(4,2)]
    # 因 3 的逆序孩子和 4 的逆序孩子相同,即 {3:[1,2], 4:[1,2]}
    # 所以可以一次排序:可以通过移动数组某一连续部分,使得数组有序
    def helper(nums):
        # 为了避免重复元素的扰乱,为每个数组元素分配id,最终数组变成[(x0,0), (x1,1), ..., (xn,n)]
        ipt = [(a, b) for a, b in zip(nums, range(len(nums)))]
        x = reversePairs(ipt)
        y = list(x.values())
        # 若逆序数为0,或每个逆序头的孩子相同,则可一步排序
        return len(y) == 0 or y.count(y[0]) == len(y)

    return helper(nums) or helper(list(reversed(nums)))


# 测试
a = [3, 4, 4, 5, -2, -1]  # True
b = [1, 3, 5, 2, 4, 6]  # False
c = [1, 2, 3, 4, 5, 6, 7]  # True
d = [3, 4, 5, 6, 7, 1, 2]  # True
e = [5, 6, 7, 3, 4, 1, 2]  # False
f = [1, 2, 5, 6, 7, 3, 4]  # True
h = [3, 4, 1, 2, 5, 6, 7]  # True
i = [5, 6, 7, 1, 2, 3, 4]  # True
j = [7, 6, 5, 2, 1, 4, 3]  # True
l = (a, b, c, d, e, f, h, i, j)
for k in l:
    print(can_sort_by_one_move(k))



全部评论

(3) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐