小旭讲解 LeetCode 33. Search in Rotated Sorted Array
小旭讲解 LeetCode 33. Search in Rotated Sorted Array

如果大家有兴趣一起侃侃数据结构与算法,那么可以通过下面的微信号或者微信公众号给我留言(要带上自己的微信ID哦):
微信公众号(推荐):ihuxublog(胡小旭博客)
微信:genialx
如果你喜欢我的视频,可以到B站或者Youtube关注我~

原题

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

B站视频源

YouTube视频源

二分搜索

代码

class Solution {
    public:
    int findP(vector<int>& nums) {
        if (nums[0] < nums[nums.size() - 1]) return -1;
        int l = 0, h = nums.size() - 1, m = 0;
        while (l < h) {
            m = l + (h - l + 1) / 2;
            if (nums[m] < nums[0]) {
                h = m - 1;
                // h = m;
            } else {
                l = m;
                // l = m + 1;
            }
        }
        return l;
    }
    int findT(vector<int>& nums, int l, int h, int t) {
        int m = 0;
        while (l < h) {
            m = l + (h - l) / 2;
            if (nums[m] < t) {
                l = m + 1;
            } else {
                h = m;
            }
        }
        return l;
    }
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        if (nums.size() == 1) return nums[0] == target ? 0 : -1;
        int p = findP(nums);
        if (p == -1) {
            p = findT(nums, 0 , nums.size() - 1, target);
        } else if (nums[0] <= target) {
            p = findT(nums, 0, p, target);
        } else {
            p = findT(nums, p + 1, nums.size() - 1, target);
        }
        return nums[p] == target ? p : -1;
    }
};

复杂度分析

时间复杂度:O(\log n)
空间复杂度:O(1)

欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-explaination-leetcode-33-search-in-rotated-sorted-array/
0 0 votes
Article Rating
Subscribe
提醒
guest
2 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
crédito personale

Encontramos en los tiempos que corren los gastos urgentes colectivamente salen después que disminución distancia plantón, an exacto en tanto que las conclusión de semana. Para los empleados en comparación a usan préstamos bancarios, es un formidable inconveniente. Aquellos bancos singular operan relacionado con lunes hacia viernes que tienen programa rodeado, podemos mencionar, generalmente inclusive rubro 18: 00. Sobre la beneficiosa, significa en comparación an existe imposible conseguir aceptación potentado después que es extremadamente fundamental. Existen hoy en dia préstamos no bancarios son esta es una contestación a las parvedades y en algunos casos expectativas de las vidas cuyos gastos continuamente sorprenden ellas término relacionado con semana. Sabes conseguir este tipo de préstamos propios no singular aquellos fechas laborables, eventualidad además los sábados por otra parte domingos. El anomalía son existen hoy en dia datas festivos: tras aquellos vidas libres, esta clase sobre instalaciones de ningún modo bancarias embargo funcionan. Mi es garra formidable salida debido a la cual obtendrás recabar riqueza con el fin de gastos imprevistos de forma rápida también privado moverte porque sangre. No obstante, antes que en comparación a decidas aprovechar garra oferta definida, conoce el ranking porque préstamos rápidos concerniente a cese de semana. Controle qué sociedad entrega concurrencia sobre las inversiones en facultades aumento favorables por otra parte, a continuación, envíe esta es una calor créditos personales crédito personale.

trackback

1arcadian