找出字符串

[编程题]找出字符串

热度指数：7288 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个string数组str,其是由一个排过序的字符串数组插入了一些空字符串得到的，同时给定数组大小n和需要查找的string x，请用时间复杂度在log级别的算法返回该串的位置(位置从零开始)。

测试样例：

["a","b","","c","","d"],6,"c"

返回：3

算法知识视频讲解

Python

恭喜你又收割一个offer！

log复杂度，锁定 快排，堆排，归并，二分, 这里考虑快速排序:
# -*- coding:utf-8 -*-

class Finder:
    def findString(self, s, n, x):
        # write code here
        left = []
        right = []
        for i in range(n):
            if s[i] > x:
                right.append(s[i])
            elif s[i] < x:
                left.append(s[i])
            else:
                return s.index(x)
            
        if findString(left, len(left), x):
            return findString(left, len(left), x)
        return findString(right, len(right), x)

发表于 2017-07-02 21:49:41 回复(2)

Python

Yannyezixin

思路：

二分查找的变形，如果中间元素为空字符串，那么找出离它最近的非空字符串即可。

其他步骤跟二分查找一样

# -*- coding:utf-8 -*-

class Finder:
    def findString(self, s, n, x):
        if n < 1:
            return -1
        
        i = 0
        j = n - 1     
        while i <= j:
            mid = (i + j)/2
            # 移动mid位置
            if s[mid] == '':
                left = mid - 1
                right = mid + 1
                while True:
                    if left < i and right > j:
                        return -1
                    elif left >= i and s[left] != '':
                        mid = left	
                        break
                    elif right <= j and s[right] != '':
                        mid = right
                        break
                    right += 1
                    left -= 1
            if s[mid] == x:
                return mid
            elif s[mid] < x:
                i = mid + 1
            else:
                j = mid - 1
        return -1

发表于 2016-08-08 14:50:27 回复(0)