0 0 vote
Article Rating
Subscribe
提醒
guest
5 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
LincentMa

想都不带想的解法:

  1. 遍历判断,返回满足判断条件的第一个结果
  2. 返回数组第一个元素
class Solution {


    /**
     * @param String[] $letters
     * @param String $target
     * @return String
     */
    function nextGreatestLetter($letters, $target) {
        // 思路1:暴力循环
        if (false == empty($letters)) {
            foreach($letters as $each_letter) {
                if ($each_letter > $target) {
                    return $each_letter;
                }
            }
            // 没有结果默认返回第一个
            return $letters[0];
        }
    }
}

稍微想一下的解法(缩小查询范围):

  1. 二分法查询,但是不是取相等值
  2. 返回数组第一个
  3. 比较绕的点在于,对于不判断相等情况下,while的条件要不要加等号;开头和结尾循环是要+1还是-1还是不变;最后返回值是返回开头元素还是第一个元素。
class Solution {


    /**
     * @param String[] $letters
     * @param String $target
     * @return String
     */
    function nextGreatestLetter($letters, $target) {
        // 思路1:暴力循环
        // if (false == empty($letters)) {
        //     foreach($letters as $each_letter) {
        //         if ($each_letter > $target) {
        //             return $each_letter;
        //         }
        //     }
        //     // 没有结果默认返回第一个
        //     return $letters[0];
        // }
        if (false == empty($letters)) {
            $letters_count = count($letters);
            $search_start_index = 0;
            $search_end_index = $letters_count - 1;
            while ($search_start_index < $search_end_index) {
                $search_middle_index = $search_start_index + ($search_end_index - $search_start_index)  / 2;
                if ($letters[$search_middle_index] > $target) {
                    
                    $search_end_index = $search_middle_index;
                } else {
                    $search_start_index = $search_middle_index + 1;
                }
            }
            // 没有结果默认返回第一个
            if ($letters[$search_start_index] <= $target) {
                return $letters[0];
            } else {
                return $letters[$search_start_index];
            }
        }
    }
}
Last edited 1 月 之前 by LincentMa
Hao
class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        if target >= letters[-1]:
            return letters[0]
        
        for item in letters:
            if item > target:
                return item

变种二分法找应该更好一些

test

char nextGreatestLetter(vector& letters, char target) {
//1. 遍历
int num = letters.size();
//if (num <= 0)
// return letters[0];

//for (size_t i = 0; i target)
// return letter;
//}
//return letters[0];

//2. 二分
int left = 0;
int right = num – 1;
while (left target)
{
right = mid – 1;
}
else
{
left = mid + 1;
}
}
return letters[left % num];
}