Форум программистов, компьютерный форум CyberForum.ru

Определение возможности сортировки массива удалением одного элемента - C++

Восстановить пароль Регистрация
 
 
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
30.06.2016, 13:32     Определение возможности сортировки массива удалением одного элемента #1
На входе есть не менее 4 целых чисел, нужно определить, можно ли удалив не более одного элемента получить невозрастающий или неубывающий массив.

Может кто-либо реализовать это, или дать описание наиболее быстрого способа?
Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2016, 13:32     Определение возможности сортировки массива удалением одного элемента
Посмотрите здесь:

C++ Циклический буфер. Проблема с удалением элемента.
C++ Исследовать возможности адаптации различных методов сортировки к структуре исходного массива
Определение 3го по величине элемента массива C++
Из массива A удалить те цепочки нечетных элементов, в которых нет ни одного элемента из массива B C++
C++ определение минимального элемента одномерного массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 1
30.06.2016, 15:23     Определение возможности сортировки массива удалением одного элемента #2
попробовал набросать, не уверен, что всегда будет работать

C++
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
#include <algorithm>
#include <iostream>
 
int main()
{
    const int N = 4;
    int x[N] = { 1, 3, 2, 4 };
    int up[N];
 
    std::copy(x, x + N, up);
    std::sort(up, up + N);
 
    for(int i = 0; i < N; ++i)
    {
        int* t = std::find(up, up + N, x[i]);
        bool result = true;
        for(int a = 0, b = 0; a < N && b < N; ++a, ++b)
        {
            if(a == i) ++a;
            if(up + b == t)  ++b;
            if(x[a] != up[b])
            {
                result = false;
                break;
            }
        }
        if(result)
        {
            std::cout << "you can do that! throw away x[" << i << "]\n";
            for(int j = 0; j < N; ++j)
                if(j != i)
                    std::cout << x[j] << " ";
            std::cout << std::endl;
        }
    }
}
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
30.06.2016, 16:14  [ТС]     Определение возможности сортировки массива удалением одного элемента #3
Babysitter, данный код работает только если массив неубывающий. Можете словесно объяснить алгоритм, чтобы я мог доделать код ? (не очень хорошо понимаю алгоритм из кода)
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 1
01.07.2016, 10:55     Определение возможности сортировки массива удалением одного элемента #4
Ka_ktus,

ну есть исходный массив, рядом создаем его копию и сортируем по неубыванию.
моя идея была в том, что теперь если мысленно зачеркнуть элемент из исходного массива и его же из нового массива, то мы должны получить одинаковые последовательности. для этого и есть этот цикл, который из 17 строчки - он просто сравнивает два массива, но если натыкается на элемент, который мы пытаемся выкинуть, то игнорируем и сравниваем дальше.

но если нужно тупо ответить на вопрос можно или не можно, то мой метод избыточный и некрасивый. я использую дополнительно памяти ~N, да и N-проходов, стыдно короче. а меня никто не проверяет, не помогает в общем вот за один проход, с константным расходом памяти. попытался хорошо написать. если под 98 нужно компилить, то вместо auto будет typename std::iterator_traits<Iter>::value_type, а вместо лямбд - обычные функции и передать указатели на них.

C++
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
#include <iostream>
 
template <class Iter, class Pred>
bool check(Iter begin, Iter end, Pred foo)
{
    bool first_miss = true;
    auto temp = *begin;
    for(Iter it = begin; it != end - 1; ++it)
    {
        if(!foo(temp, *(it + 1)))
            if(first_miss)
            {
                first_miss = false;
                continue;
            }
            else
                return false;
        temp = *(it + 1);
    }
    return true;
}
 
int main()
{
    typedef int Type;
    const Type N = 4;
    Type x[N] = { 1, 3, 2, 4 };
 
    std::cout << " - can i throw one an make it non-decreasing?\n";
    std::cout << " - " << (check(x, x + N, [](Type a, Type b) {return a <= b;}) ? "yes, you can." : "no, you can not.") << "\n\n";
    std::cout << " - can i throw one an make it non-increasing?\n";
    std::cout << " - " << (check(x, x + N, [](Type a, Type b) {return a >= b;}) ? "yes, you can." : "no, you can not.") << "\n\n";
 
    return 0;
}
http://rextester.com/MCKEB73164
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
01.07.2016, 13:09  [ТС]     Определение возможности сортировки массива удалением одного элемента #5
Babysitter, К сожалению некорректно работает как минимум на примере 5, 1, 2, 3
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 1
01.07.2016, 15:53     Определение возможности сортировки массива удалением одного элемента #6
Ka_ktus, ага, очень хотелось не портить исходный массив, чтобы не пришлось копировать. хотелось меньше кода написать - не получилось, недостаточно продумал, стыдненько. кажется, что так неплохо:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <class Iter, class Pred>
bool check(Iter begin, Iter end, Pred foo)
{
    bool first_miss = true;
    auto temp = *begin;
    for(Iter it = begin; it != end - 1;)
    {
        if(!foo(temp, *(it + 1)))
            if(first_miss)
            {
                first_miss = false;
                if (it != begin)
                {
                    temp = *(it - 1);
                    continue;
                }
            }
            else
                return false;
        temp = *(it + 1); ++it;
    }
    return true;
}
Добавлено через 9 минут
кстати, если first_miss установлен в true перед return true; из функции - это значит, что массив уже является отсортированым.
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
01.07.2016, 16:02     Определение возможности сортировки массива удалением одного элемента #7
Цитата Сообщение от Ka_ktus Посмотреть сообщение
Можете словесно объяснить алгоритм, чтобы я мог доделать код
Можно проще.
Рассматриваем разности соседних элментов. Каждая разность либо 0, либо положительная, либо отрицательная. Считаем количество. Если количество + и - больше 1 - ответ "нет". Иначе рассматриваем подмассив из четырех элементов, где в середине меняется знак. Если знак меняется на границе массива - ответ "да". Иначе (рассматриваем для ясности пример с одним "-" он, напомню между, [1] и [2]) если [0]<=[1]<=[3] или [0]<=[2]<=[3] ответ "да". Для случая единственного "+" - аналогично. Если и + и - встречаются 1 раз - рассмотреть нужно оба.
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
02.07.2016, 12:58  [ТС]     Определение возможности сортировки массива удалением одного элемента #8
Babysitter, Вроде бы все работает, никаких контрпримеров я не нашел, но попытавшись переписать код для его работы с динамическими массивами столкнулся с некоторыми трудностями, не могли бы вы его переписать для динамических массивов, или целочисленных vector ?
(пробовал и с ссылками все оставить, и заменить ссылки на целые числа и работать просто с элементами массива, но программа начинает выдавать непредсказуемые результаты)

Добавлено через 17 часов 7 минут
Babysitter, Мне удалось самому вполне успешно переписать код для динамических массивов, но я опять нашел контрпример к вашему алгоритму. В этот раз это 5, 2, 2, 2, 2, 2, 2, 2, 1, 5 , который при удалении последнего элемента становится невозрастающим
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 1
02.07.2016, 19:01     Определение возможности сортировки массива удалением одного элемента #9
Ka_ktus, не было возможности раньше ответить. по поводу переписывания кода - это не требуется! функция принимает итераторы начала и конца(элемента после конца, если точнее). клиентский код для вектора приведу ниже. по поводу этого кейса - ты прав, краевые условия так и не рассмотрел все. вот очередная версия, возможно стоит посмотреть в сторону решения avgoor.

C++
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
#include <iostream>
#include <vector>
 
template <class Iter, class Pred>
bool check(Iter begin, Iter end, Pred foo)
{
    bool first_miss = true;
    auto temp = *begin;
    for(Iter it = begin; it != end - 1;)
    {
        if(it == end - 2 && first_miss)
            return true;
        if(!foo(temp, *(it + 1)))
            if(first_miss)
            {
                first_miss = false;
                if (it != begin)
                {
                    temp = *(it - 1);
                    continue;
                }
            }
            else
                return false;
        temp = *(it + 1); ++it;
    }
    return true;
}
 
int main()
{
    typedef int Type;
    std::vector<Type> x{5, 2, 2, 2, 2, 2, 2, 2, 1, 5};
     
    std::cout << " - can i throw one an make it non-decreasing?\n";
    std::cout << " - " << (check(x.begin(), x.end(), [](Type a, Type b) {return a <= b;}) ? "yes, you can." : "no, you can not.") << "\n\n";
    std::cout << " - can i throw one an make it non-increasing?\n";
    std::cout << " - " << (check(x.begin(), x.end(), [](Type a, Type b) {return a >= b;}) ? "yes, you can." : "no, you can not.") << "\n\n";
 
    return 0;
}
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
04.07.2016, 19:46  [ТС]     Определение возможности сортировки массива удалением одного элемента #10
Babysitter, Хмм, забавно, ваш алгоритм почему-то не сработал на простом примере с 1, 2, 3, 4, 0, 5.
Хотя раньше вроде работало. странно.
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 1
05.07.2016, 15:23     Определение возможности сортировки массива удалением одного элемента #11
Ka_ktus, похоже у этого решения оказалась серьезная болезнь, но просто из принципа попробую довести его до конца. в момент, когда происходит мисс программа не может понять который из двух элементов плохой, кого нужно выбрасывать. кода стало больше, и я добавил тестов, а то это уже как-то печально становится... концепт плохой, будет работать везде, где есть произольный доступ.

C++
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
#include <iostream>
#include <vector>
#include <cassert>
#include <stdexcept>
#include <list>
 
 
template <class Iter, class Pred>
bool check(Iter begin, Iter end, Pred foo, bool hit = false)
{
    if (!hit && end - begin < 3)
        return true;
 
    for (Iter cur = begin + 1; cur < end; ++cur)
    {
        if (!foo(*(cur - 1), *cur))
        {
            if (hit)
                return false;
            else
            {
                hit = true;
                bool res = true;
                if (cur - 1 == begin)
                {
                    res = check(begin + 1, end, foo, hit);
                    if (res)
                        return true;
                    res = res || foo(*(cur - 1), *(cur + 1));
                }
                else if (cur + 1 == end)
                {
                    res = check(begin, cur, foo, hit);
                    if (res)
                        return true;
                    res = res || foo(*(cur - 2), *cur);
                }
                else
                    res = foo(*(cur - 2), *cur) || foo(*(cur - 1), *(cur + 1));
                if (!res)
                    return false;
            }
        }
    }
    return true;
}
 
typedef int Type;
 
template <class Iter>
void test_check(Iter begin, Iter end, bool r1, bool r2)
{
    assert(check(begin, end, [](Type a, Type b) { return a <= b; }) == r1);
    assert(check(begin, end, [](Type a, Type b) { return a >= b; }) == r2);
}
 
int main()
{
    std::vector<Type> x;
 
    // ** testing **
    // ** first element **
    x = {5, 1, 2, 3, 4};
    test_check(x.begin(), x.end(), true, false);    
    x = {0, 5, 4, 3, 2};
    test_check(x.begin(), x.end(), false, true);
    // \first element
    
    // ** last element **
    x = {1, 2, 3, 4, 0};
    test_check(x.begin(), x.end(), true, false);
    x = {5, 4, 3, 2, 7};
    test_check(x.begin(), x.end(), false, true);
    // \last element
    
    // ** one/two elements **
    x = { 1 };
    test_check(x.begin(), x.end(), true, true);
    x = {0, 1};
    test_check(x.begin(), x.end(), true, true);
    x = {1, 0};
    test_check(x.begin(), x.end(), true, true);
    // \one/two elements
    
    // ** regular cases **
    x = {5, 2, 2, 2, 2, 2, 2, 2, 1, 5};
    test_check(x.begin(), x.end(), false, true);    
    x = {1, 2, 3, 4, 0, 5};
    test_check(x.begin(), x.end(), true, false);   
    x = { 1, 5, 2, 3, 4 };
    test_check(x.begin(), x.end(), true, false);    
    x = { 5, 6, 1, 2, 3 };
    test_check(x.begin(), x.end(), false, false);
    // \regular cases
 
    return 0;
}
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
05.07.2016, 21:55  [ТС]     Определение возможности сортировки массива удалением одного элемента #12
Babysitter, Спасибо! Все работает!
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
06.07.2016, 08:57     Определение возможности сортировки массива удалением одного элемента #13
C++
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
//На входе есть не менее 4 целых чисел, нужно определить, можно ли удалив
//не более одного элемента получить невозрастающий или неубывающий массив.
//Может кто-либо реализовать это, или дать описание наиболее быстрого способа?
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <numeric>
#include <deque>
///////////////////////////////////////////////////////////////////////////////
typedef std::deque  < int   >   T_numbers;
///////////////////////////////////////////////////////////////////////////////
T_numbers   make_rand_numbers()
{
    T_numbers   res     { 1, 2, 3, 4, 5, 6, 7 };
 
    if  (
            rand() % 2
        )
    {
        std::reverse
            (
                res.begin   (),
                res.end     ()
            );
    }//if
 
    int     anomalies_total     =   rand()  %   4;
 
    for( int  i{}; i < anomalies_total; ++i )
    {
        int     rand_ind    =       rand()
 
                                %   (
                                        res.size() - 1
                                    );
 
        std::swap
            (
                res[ rand_ind           ],
                res[ rand_ind   +   1   ]
            );
    }//for
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
bool    sequence_is_monotonic_but_one_element( T_numbers    const   &   numbers )
{
    T_numbers   diff;
 
    std::adjacent_difference
        (
            numbers.begin       (),
            numbers.end         (),
            std::back_inserter  ( diff )
        );
 
    diff.pop_front();
 
    return          std::count_if
                        (
                            diff.begin  (),
                            diff.end    (),
                            []          ( auto  elem )
                            {
                                return  elem    <   0;
                            }
                        )
 
                ==  1
 
            ||      std::count_if
                        (
                            diff.begin  (),
                            diff.end    (),
                            []          ( auto  elem )
                            {
                                return  elem    >   0;
                            }
                        )
 
                ==  1;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        auto    numbers     =   make_rand_numbers();
 
        std::copy
            (
                numbers.begin               (),
                numbers.end                 (),
                std::ostream_iterator<int>  ( std::cout,    "\t" )
            );
 
        std::cout   <<  std::boolalpha
                    <<  sequence_is_monotonic_but_one_element( numbers )
                    <<  std::endl;
 
        system("pause");
    }//for
}
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 1
06.07.2016, 11:17     Определение возможности сортировки массива удалением одного элемента #14
упд. сразу не понял, что в этом варианте если последовательность уже упорядочена, то ответ false

Добавлено через 13 минут
в продакшн рановато. вопрос был можно ли удалив не более одного элемента. то есть если последовательность уже является упорядоченой, то ответ true. плюс частные случаи же
C++
1
2
3
{ 1 }   false
{ 1, 2 }   true
{ 1, 2, 3 }   false
Добавлено через 9 минут
Цитата Сообщение от Babysitter Посмотреть сообщение
частные случаи же
вопрос снят. не менее 4 целых чисел - устал я что-то.
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
06.07.2016, 11:56     Определение возможности сортировки массива удалением одного элемента #15
Ну, если жалко памяти, то, с учетом
Цитата Сообщение от Babysitter Посмотреть сообщение
удалив не более одного элемента
см. ниже.
Кстати, условие
Цитата Сообщение от Babysitter Посмотреть сообщение
не менее 4 целых чисел
совершенно надуманное, моя программа считает для любой последовательности. (Пустую я принял монотонной.)
C++
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
//На входе есть не менее 4 целых чисел, нужно определить, можно ли удалив
//не более одного элемента получить невозрастающий или неубывающий массив.
//Может кто-либо реализовать это, или дать описание наиболее быстрого способа?
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <numeric>
///////////////////////////////////////////////////////////////////////////////
T_numbers   make_rand_numbers()
{
    T_numbers   res     { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
    if  (
            rand() % 2
        )
    {
        std::reverse
            (
                res.begin   (),
                res.end     ()
            );
    }//if
 
    int     anomalies_total     =   rand()  %   5;
 
    for( int  i{}; i < anomalies_total; ++i )
    {
        int     rand_ind    =       rand()
 
                                %   (
                                        res.size() - 1
                                    );
 
        std::swap
            (
                res[ rand_ind           ],
                res[ rand_ind   +   1   ]
            );
    }//for
 
    return  {
                res.begin(),
                res.begin()     +   rand()  %   res.size()
            };
}
///////////////////////////////////////////////////////////////////////////////
bool    sequence_is_monotone_except_may_be_one_element( T_numbers    const   &   numbers )
{
    bool    bool_res    =   numbers.size()  <=  2;
 
    if( !bool_res )
    {
        int     count_pos{};
        int     count_neg{};
 
        for( size_t  i{1}; i < numbers.size(); ++i )
        {
            auto    diff    =       numbers[i]
                                -   numbers[i - 1];
 
            if( !diff )
            {
                continue;
            }
 
            diff    >   0
                ?   ++count_pos
                :   ++count_neg;
 
            bool_res    =       std::min    (
                                                count_pos,
                                                count_neg
                                            )
                            <=  1;
 
            if( !bool_res )
            {
                return  bool_res;
            }
        }//for
    }//if
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        auto    numbers     =   make_rand_numbers();
 
        std::copy
            (
                numbers.begin               (),
                numbers.end                 (),
                std::ostream_iterator<int>  ( std::cout,    "\t" )
            );
 
        std::cout   <<  std::boolalpha
                    <<  sequence_is_monotone_except_may_be_one_element( numbers )
                    <<  std::endl;
 
        system("pause");
    }//for
}
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
06.07.2016, 13:34     Определение возможности сортировки массива удалением одного элемента #16
Mr.X, Последовательность: {1, 1, 0, 0, 1, 1} пройдет ваш тест, а не должна. Выше писал, что еще нужно проверять.

Добавлено через 15 минут
UPD: минимальная последовательность, воспроизводящая проблему: {3, 4, 1, 2}
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
06.07.2016, 16:19     Определение возможности сортировки массива удалением одного элемента #17
Цитата Сообщение от avgoor Посмотреть сообщение
Mr.X, Последовательность: {1, 1, 0, 0, 1, 1} пройдет ваш тест, а не должна. Выше писал, что еще нужно проверять.
Добавлено через 15 минут
UPD: минимальная последовательность, воспроизводящая проблему: {3, 4, 1, 2}
А, да, замечание справедливое.
notAll
176 / 65 / 16
Регистрация: 27.05.2016
Сообщений: 182
Завершенные тесты: 2
06.07.2016, 17:35     Определение возможности сортировки массива удалением одного элемента #18
Как то так:
C++
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
#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cassert>
 
template <typename It>
bool check(It first, It last)
{
    auto length = std::distance(first, last);
    assert(length >= 4);
 
    using value_type = typename std::iterator_traits<It>::value_type;
    auto final_check = [](auto f, auto l) { return std::is_sorted(f, l) ||
                std::is_sorted(f, l, std::greater<value_type>());
    };
 
    if (final_check(first, last)) return true;
    else
    {
        for (int i = 0; i < length; ++i)
        {
            std::vector<value_type> v{first, last};
            v.erase(v.begin() + i);
            if (final_check(v.begin(), v.end()))
                return true;
        }
    }
    return false;
}
 
int main()
{
    int arr[] = {1, 2, 3, 4, 0, 5};
    std::cout << std::boolalpha;
    std::cout << check(std::begin(arr), std::end(arr));
}
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
06.07.2016, 18:07     Определение возможности сортировки массива удалением одного элемента #19
notAll, А ничего, что вы задачу, решаемую за линейное время решаете за квадратичное? Измените main вот так:
C++
1
2
3
4
5
6
7
8
9
int main()
{
    const int size = 1000000;
    int arr[size];
    std::iota(arr, std::end(arr) - 1, 0);
    arr[size - 1] = -1;
    std::cout << std::boolalpha;
    std::cout << check(std::begin(arr), std::end(arr));
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2016, 11:22     Определение возможности сортировки массива удалением одного элемента
Еще ссылки по теме:

C++ Определение минимального элемента одномерного массива
C++ Определение первого из столбцов, не содержащих ни одного отрицательного элемента
C++ Определение индекса элемента массива, имеющего максимальное значение (функция)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
notAll
176 / 65 / 16
Регистрация: 27.05.2016
Сообщений: 182
Завершенные тесты: 2
07.07.2016, 11:22     Определение возможности сортировки массива удалением одного элемента #20
Тогда так:
C++
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
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
 
template <typename It>
bool check(It first, It last)
{
    auto it = std::is_sorted_until(first, last);
    if (it != last)
    {
        //1 - delete first broken element
        It prev, next;
        prev = next = it;
        if (*--prev < *++next)
            return std::is_sorted_until(next, last) == last;
 
        //2 - delete prev element before broken
        prev = it;
        if ((prev - first) > 1 && *----prev < *it)
            return std::is_sorted_until(next, last) == last;
        else if ((prev - first) == 1)
            return std::is_sorted_until(it, last) == last;
 
        return false;
    }
 
    return true;
}
 
template <typename T>
void print(const std::vector<T> &v)
{
    for (const auto &i : v)
        std::cout << i << ", ";
}
 
int main()
{
    std::vector<std::vector<int>> vec {
        {1,2,3,4,5}, //true
        {1,2,3,4,5,0}, //true
        {1,2,3,4,0,5}, //true
        {42,1,2,3,4,5}, //true
        {1,42,2,3,4,5}, //true
        {42,1,2,3,4,5,0}, //false
        {1,42,2,3,4,42,5}, //false
        {1,1,0,0,1,1}, //false
        {3,4,1,2} //false
    };
 
    std::cout << std::boolalpha;
    for (auto &v : vec) {
        print(v);
        std::cout << " - " << check(std::begin(v), std::end(v)) << "\n";
    }
}
Добавлено через 11 минут
И с проверкой на обратную сортировку:
C++
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
#include <iostream>
#include <vector>
#include <functional>
#include <iterator>
#include <algorithm>
 
template <typename It, typename Comparator =
          std::less<typename std::iterator_traits<It>::value_type>>
bool check_impl(It first, It last, Comparator comp = Comparator())
{
    auto it = std::is_sorted_until(first, last, comp);
    if (it != last)
    {
        //1 - delete first broken element
        It prev, next;
        prev = next = it;
        if (comp(*--prev, *++next))
            return std::is_sorted_until(next, last, comp) == last;
 
        //2 - delete prev element before broken
        prev = it;
        if ((prev - first) > 1 && comp(*----prev, *it))
            return std::is_sorted_until(next, last, comp) == last;
        else if ((prev - first) == 1)
            return std::is_sorted_until(it, last, comp) == last;
 
        return false;
    }
 
    return true;
}
 
template <typename It>
bool check(It first, It last)
{
    if (!check_impl(first, last))
        return check_impl(first, last,
                          std::greater<typename std::iterator_traits<It>::value_type>());
    return true;
}
 
template <typename T>
void print(const std::vector<T> &v)
{
    for (const auto &i : v)
        std::cout << i << ", ";
}
 
int main()
{
    std::vector<std::vector<int>> vec {
        {1,2,3,4,5}, //true
        {1,2,3,4,5,0}, //true
        {1,2,3,4,0,5}, //true
        {42,1,2,3,4,5}, //true
        {1,42,2,3,4,5}, //true
        {42,1,2,3,4,5,0}, //false
        {1,42,2,3,4,42,5}, //false
        {1,1,0,0,1,1}, //false
        {3,4,1,2} //false
    };
 
    std::cout << std::boolalpha;
    for (auto &v : vec) {
        print(v);
        std::cout << " - " << check(std::begin(v), std::end(v)) << "\n";
    }
}
Yandex
Объявления
07.07.2016, 11:22     Определение возможности сортировки массива удалением одного элемента
Ответ Создать тему

Метки
c++, алгоритм, сортировка
Опции темы

Текущее время: 08:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru