【Python】抛砖引玉-连续有序数组的排序问题

[本文出自天外归云的博客园]

有这么一个连续有序数组,比如1,2,3,4,5,6,7,8,9。把7,8,9移到最前面,就是7,8,9,1,2,3,4,5,6。让你找出某个元素在数组中的索引,如果没有则返回-1

python我的解法是这样的,先把那个分界点找出来,然后切成两个数组,判断下该在哪个数组里进行二分查找,然后进行二分查找:

# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
def find_sub_arr(_arr):
    sub_arr1 = []
    sub_arr2 = []
    i = 0
    while i < len(_arr) - 1:
        if _arr[i+1] != _arr[i] + 1:
            sub_arr1 = _arr[:i+1]
            sub_arr2 = _arr[i+1:]
        i += 1
    return sub_arr1, sub_arr2

def binary_search(_arr, l, r, _num):
    if r >= l:
        mid = int(l + (r - l)/2)
        if _arr[mid] == _num:
            return mid
        elif _arr[mid] > _num:
            return binary_search(_arr, l, mid-1, _num)
        else:
            return binary_search(_arr, mid+1, r, _num)
    else:
        return -1

def index_of(_arr, _num):
    sub1, sub2 = find_sub_arr(arr)
    if _num >= sub1[0]:
        print(f"find {_num} in {sub1}")
        return binary_search(sub1, 0, len(sub1)-1, _num)
    elif _num >= sub2[0]:
        print(f"find {_num} in {sub2}")
        return len(sub1) + binary_search(sub2, 0, len(sub2)-1, _num)
    else:
        return -1

arr = [7,8,9,1,2,3,4,5,6]
print(f"arr is {arr}")
for a in arr:
    ind = index_of(arr, a)
    print(f"index {a} is {ind}")
    print("——————————————————")

看看还有什么更好的解法吗?

Original: https://www.cnblogs.com/LanTianYou/p/16373751.html
Author: 天外归云
Title: 【Python】抛砖引玉-连续有序数组的排序问题

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/15741/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

最近整理资源【免费获取】:   👉 程序员最新必读书单  | 👏 互联网各方向面试题下载 | ✌️计算机核心资源汇总