cs-notes/leetcode/0081.cpp at master · Hansimov/cs-notes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
= My 8ms C++ solution (o(logn) on average, o(n) worst case) - LeetCode Discuss
    https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28218/My-8ms-C%2B%2B-solution-(o(logn)-on-average-o(n)-worst-case)
    https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28218/My-8ms-C++-solution-(o(logn)-on-average-o(n)-worst-case)/112460
= leetcode 81 - TempterCyn的博客 - CSDN博客
    https://blog.csdn.net/TempterCyn/article/details/84728538
*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <set>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <limits.h>

using namespace std;

bool searchInRotatedSortedArray(vector<int>& v, int t) {
    int n = v.size();
    if (v.size() == 0) return false;

    int l=0, r=n-1, m;

    while (l<r) {
        m = l+(r-l)/2;
        if (v[m] == t) return true;
        if (v[l]<v[m]) {
            if (v[m]<=v[r]) {
                if (v[l]<=t && v[m]>t)
                    r = m-1;
                else if (v[m]<t && v[r]>=t)
                    l = m+1;
                else
                    return false;
            } else { // v[m]>v[r], then there must be v[l]>=v[r]
                if (v[l]<=t && v[m]>t)
                    r = m-1;
                else
                    l = m+1;
            }
        } else if (v[l]>v[m]) { // then there must be v[m]<=v[r] && v[l]>=v[r]
            if (t<v[l] && t>v[r])
                return false;
            else if (t<=v[r] && t>v[m])
                l = m+1;
            else
                r = m-1;
        } else { // v[l]==v[m]
            if (v[m]==v[r]) {
                l++; r--;
            } else if (v[m]<v[r]) {
                if (t>v[m] && t<=v[r])
                    l = m+1;
                else
                    r = m-1;
            } else { // v[m]>v[r]
                if (t<v[m] && t>v[r])
                    return false;
                else
                    l = m+1;
            }
        }
    }

    return v[l]==t?true:false;
}


string filename = "0081.txt";
const auto& myFunc = searchInRotatedSortedArray;

int main() {
    string vin, nrin;
    vector<vector<int>> vv;
    vector<int> vn;
    vector<int> vr;

    ifstream fp;
    fp.open(filename);

    int d;
    while (getline(fp, vin, '\n')) {
        stringstream sv(vin);

        vector<int> vvi = {};
        while (sv >> d) {
            vvi.push_back(d);
        }
        vv.push_back(vvi);

        getline(fp, nrin, '\n');
        stringstream snr(nrin);
        snr >> d;
        vn.push_back(d);
        snr >> d;
        vr.push_back(d);
    }
    fp.close();

    printf("%s\t%s\t%s\t%s\n", "T","L", "√", "?");
    printf("--- --- --- --- \n");
    int correct_cnt=0;
    for (int i=0; i<vr.size(); ++i) {
        int res = myFunc(vv[i],vn[i]);
        bool is_correct = (res==1)==vr[i];
        printf("%d\t%d\t%d\t%d\n", is_correct, 2*i+1, vr[i], res);
        if (is_correct) ++correct_cnt;
    }
    printf("--- --- --- --- \n");
    printf("%s\t%d/%d\n", correct_cnt==vr.size()?"√":"×",correct_cnt, vr.size());

    return 0;
}