专栏首页desperate633LintCode 恢复旋转排序数组题目分析代码

LintCode 恢复旋转排序数组题目分析代码

题目

给定一个旋转排序数组,在原地恢复其排序。

说明 什么是旋转数组? 比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

样例 [4, 5, 1, 2, 3]->[1, 2, 3, 4, 5]

分析

这道题主要考察观察能力,显然旋转数组,不管怎么旋转,由于之前是排好序的,所以找到比第一个数小的第一个数一定是整个排序数组中最小的数。所以,只要找到最小的那个数,然后把前面的数全部按顺序加到后面,最后再将前面的数删除就可以了。

代码

public class Solution {
    /**
     * @param nums: The rotated sorted array
     * @return: void
     */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        // write your code
        int temp = nums.get(0);
        int i;
        for( i = 0;i<nums.size();i++){
            if(nums.get(i)<temp)//找到最小的数
                break;
        }
        if(i!=nums.size()){
        for(int j=0 ; j<i;j++)
           nums.add(nums.get(j));
        nums.subList(0, i).clear();
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 280. Wiggle Sort IIsolution

    复杂度 时间 O(N) 空间 O(1) 思路 题目对摇摆排序的定义有两部分: 如果i是奇数,nums[i] >= nums[i - 1] 如果i是偶数...

    desperate633
  • LintCode 奇偶分割数组题目分析代码

    desperate633
  • LintCode 寻找缺失的数题目分析方法二 交换法

    给出一个包含 0 .. N 中 N 个数的序列,找出0 .. N 中没有出现在序列中的那个数。

    desperate633
  • leetcode-628-Maximum Product of Three Numbers

    chenjx85
  • LeetCode 80. 删除排序数组中的重复项 II

    给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

    Michael阿明
  • LeetCode-31 下一个排列

    今天我们学习第31题下一个排列,这是一个中等的数组题。我们先看看这道题的题目描述。

    用户3470542
  • LeetCode 448. 找到所有数组中消失的数字

    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    Michael阿明
  • leetcode 217 Contains Duplicate 数组中是否有重复的数字

    Contains Duplicate Total Accepted: 26477 Total Submissions:...

    流川疯
  • 旋转排序的数组

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    羽翰尘
  • 移动零

    一份执着✘

扫码关注云+社区

领取腾讯云代金券