java - 【算法题】给定int数组,移除不超过一个元素后,判断是否存在自增序列
怪我咯
怪我咯 2017-04-18 10:52:52
0
4
723

没什么思路啊,题目如下
Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

[time limit] 4000ms (js)
[input] array.integer sequence

Guaranteed constraints:
2 ≤ sequence.length ≤ 105,
-105 ≤ sequence[i] ≤ 105.

[output] boolean

Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

有个思路:2层循环,第一循环移除元素,第二层循环判断移除这个元素后是否有自增序列。

怪我咯
怪我咯

走同样的路,发现不同的人生

全員に返信(4)
PHPzhong

アイデアを提供してください

差分ごとの配列を作成します: たとえば、a=[1,3,2,1]、差分の後、[2,-1,-1] が得られます

いわゆる要素の削除とは、差分配列の先頭または末尾を削除すること、または 2 つの隣接する要素を 1 つの要素に追加することを意味します。

したがって、差分配列に複数の負の数がある場合は機能しませんが、負の数が存在しない場合は、負の数が存在する場合のみ上記の操作が実行されます。削除するか正の数にマージすると機能します

このようにして、時間計算量は O(n) に削減できます

いいねを押す +0
迷茫

O(n) 時間で実行可能:O(n) 时间做到:

  1. 对每个相邻的 [a, b],判断是否 a >= b。这样的数对破坏严格递增性。如果这样的数对超过一个,返回false。如果一个也没有,返回true。

  2. 如果1中只有一对 [a0, b0],判断 "移除a0b0

  3. 隣接する各 [a, b] について、a >= b かどうかを判断します。このような数値のペアは厳密な増分性を破壊します。そのようなペアが複数ある場合は、false を返します。何もない場合は true を返します。
  • 🎜1 に [a0, b0] のペアが 1 つしかない場合、「a0 または b0 を削除した後も増加するかどうか」を判断します。 >」と返します 🎜🎜 🎜
  • いいねを押す +0
    Ty80

    結果は正しいですが、指定された時間を超えています。もっと良い方法はありますか?

    リーリー

    時間計算量が O(n) のメソッド

    リーリー
    いいねを押す +0
    左手右手慢动作

    これは逆数の数を数えているのでしょうか?

    いいねを押す +0
    人気のチュートリアル
    詳細>
    最新のダウンロード
    詳細>
    ウェブエフェクト
    公式サイト
    サイト素材
    フロントエンドテンプレート