665. Non-decreasing Array (Easy)

https://leetcode.com/problems/non-decreasing-array/

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i="" <="" n).="" p="">

Example 1:

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10,000].

Solutions

class Solution {

    // Find out the first descending pair and change it to conform the ascending order.
    // Then move on the check whether this change makes the subsequence ascendingly ordered or not.
    // We have two options of changing the value, slot i and i + 1. We update them in order and
    // validate the sequence after manipulation respectively. As long as either of the two sequences are
    // organized as ascending order, we can return true.

    public boolean checkPossibility(int[] nums) {
        if (nums.length <= 2) {
            return true;
        }

        // It is wrongly described in the problem, we should take 0 position into account.
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] <= nums[i + 1]) {
                continue;
            }

            int tmp = nums[i];
            nums[i] = nums[i + 1];

            if (checkAscending(nums)) {
                return true;
            }

            nums[i] = tmp;
            nums[i + 1] = tmp;

            if (checkAscending(nums)) {
                return true;
            }

            return false;
        }

        // Due to the fact that no descending pairs is found, return true directly.
        return true;
    }

    public boolean checkAscending(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return false;
            }
        }

        return true;
    }
}

Incorrect Solutions

class Solution {

    // Incorrect idea of counting the descending pairs

    public boolean checkPossibility(int[] nums) {
        if (nums.length <= 2) {
            return true;
        }

        // keep the count of decending pairs
        int count = 0;

        // It is wrongly described in the problem, we should take 0 position into accounnt.
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                count++;
            }
        }

        if (count > 1) {
            return false;
        }

        return true;
    }
}

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""