精华内容
下载资源
问答
  • LeetCode旋转数组

    2019-02-20 17:13:47
    LeetCode旋转数组问题描述解题思路代码实现 问题描述         给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。尽可能...

    问题描述

            给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的原地算法。

    示例1
            输入: [1,2,3,4,5,6,7] 和 k = 3
            输出: [5,6,7,1,2,3,4]
            解释:
            向右旋转 1 步: [7,1,2,3,4,5,6]
            向右旋转 2 步: [6,7,1,2,3,4,5]
            向右旋转 3 步: [5,6,7,1,2,3,4]

    示例2
            输入: [-1,-100,3,99] 和 k = 2
            输出: [3,99,-1,-100]
            解释:
            向右旋转 1 步: [99,-1,-100,3]
            向右旋转 2 步: [3,99,-1,-100]

    解题思路

            这是一道比较常见的题,很多教材的课后习题中也有这道题目,第一次遇见这道题时我也是采用暴力算法,循环求解,看到翻转解法时很不能理解,不知道为什么别人能想出这样的算法,现在感觉多少有些了解了,尝试讲一下。
            数组右移k个位置,我们只看最后结果,就是数组最后的k位平移到了数组最前面的k位。数组最前面的(length-k)位向后平移k个位置。按照这样的想法,我们先将前面的(length-k)翻转,为最后一次翻转产生的逆序做提前的翻转,使之翻转后仍是原有顺序,第二个翻转也是这个道理。如果这样看的话,我们先执行一次全体翻转,在执行1,2步翻转也是一样的,只不过是翻转的起始位置发生了变化。翻转本省就带有位置的移动,这是十分重要的一点。

    代码实现

    public class TranslationArray {
    
        public static void main(String[] agrs){
    
            int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            
            translationArray(nums, 6);
            
            for (int num : nums) {
                System.out.println(num);
            }
        }
    
        public static void translationArray(int[] nums, int k){
        	// 当k大于数组的长度时,避免产生数组下标越界
            k %= nums.length;
            // 当位移为空或者数组长度小于2时,不进行操作
            if(k == 0 || nums.length <= 1) return;
            // 翻转前(length - k)位
            reverse(nums, 0, nums.length - 1 - k);
            // 翻转后k位
            reverse(nums, nums.length - k, nums.length -1);
            // 翻转整个数组
            reverse(nums, 0, nums.length -1);
        }
    
        public static void reverse(int[] array, int start, int end){
            int temp, mid = (end - start) / 2;
            // 依次交换首位位置元素,向中间循环
            for(int i = 0; i <= mid; i++){
                temp = array[start + i];
                array[start + i] = array[end - i];
                array[end - i] = temp;
            }
        }
    }
    
    展开全文
  • Leetcode 旋转数组的最小数字 文章目录Leetcode 旋转数组的最小数字题目题解第一种暴力解法,时间复杂度 O(n)第二种二分查找,时间复杂度 O(logn) 题目 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为...

    Leetcode 旋转数组的最小数字

    题目

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。

    示例 1:

    输入:[3,4,5,1,2]
    输出:1
    示例 2:

    输入:[2,2,2,0,1]
    输出:0

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

    题解

    • 复杂度分析

    时间复杂度上限 O(n) ,整个数组对比一遍

    时间复杂度下限 O(logn),因为数组是有序的,可以使用二分查找

    • 定位问题

    数组的查找问题

    • 算法思维

    变形二分查找,一是旋转,二是有相同的元素

    • 代码实现

    第一种暴力解法,时间复杂度 O(n)

        public static int minArray(int[] numbers) {
            int res = numbers[0];
            for (int i = 1; i < numbers.length; i++) {
                if (res > numbers[i]) {
                    res = numbers[i];
                }
            }
            return res;
        }
    

    运行时间 1ms

    消耗内存 39.3 MB

    第二种二分查找,时间复杂度 O(logn)

    分为三种情况

    • numbers[mid] < numbers[high] 说明最小值在 low, mid 区间
    • numbers[mid] > numbers[high] 说明最小值在 mid+1, high 区间
    • numbers[mid] == numbers[high] 说明两个区间都有可能继续递归
        public static int minArray(int[] numbers) {
            return findMinArray(numbers,0,numbers.length - 1);
        }
    
        public static int findMinArray(int[] numbers, int low, int high) {
            if (low == high) {
                return numbers[low];
            }
            int mid = low + ((high - low) >> 1);
            if (numbers[mid] < numbers[high]) { // 说明最小值在 low, mid 区间
                return findMinArray(numbers, low, mid);
            } else if (numbers[mid] > numbers[high]) {// 说明最小值在 mid+1, high 区间
                return findMinArray(numbers, mid + 1, high);
            } else {// 相等说明两个区间都有可能继续递归
                int a = findMinArray(numbers, low, mid);
                int b = findMinArray(numbers, mid + 1, high);
                return a < b ? a : b;
            }
        }
    

    运行时间 0ms

    消耗内存39.8 MB

    展开全文
  • class Solution(object): def rotate(self, nums, k): """ Do not return anything, modify nums in-place instead. """  k = k%len(nums)  nums[:] = nums[-k:]+nums[:-k]
  • LeetCode 旋转数组

    2018-08-02 10:20:39
    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例 1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向...

    传送门

    题目描述

    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    示例 1:

    输入: [1,2,3,4,5,6,7] 和 k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1 步: [7,1,2,3,4,5,6]
    向右旋转 2 步: [6,7,1,2,3,4,5]
    向右旋转 3 步: [5,6,7,1,2,3,4]

    示例 2:

    输入: [-1,-100,3,99] 和 k = 2
    输出: [3,99,-1,-100]
    解释:
    向右旋转 1 步: [99,-1,-100,3]
    向右旋转 2 步: [3,99,-1,-100]

    说明:
    • 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    • 要求使用空间复杂度为 O(1) 的原地算法。

    假·解答一

    先来看一种不符合题目要求的解法

    • 时间复杂度:O(n)
    • 控件复杂度:O(n)

    因为第i个元素向右移动k个位置的位置是(i + k) % nums.length,所以我们可以创建一个大小为nums.length的辅助数组tmp,然后遍历数组nums,把nums[i]复制到tmp[(i + k) % nums.length)],最后用tmp覆盖nums就行了。

    class Solution {
        public void rotate(int[] nums, int k) {
            if (nums.length == 0 || (k %= nums.length) == 0) return;
            int[] tmp = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                tmp[(i + k) % nums.length] = nums[i];
            }
            System.arraycopy(tmp, 0, nums, 0, nums.length);
        }
    }

    假·解答二

    再来一种不符合题目要求的解法

    • 时间复杂度:O(n)
    • 空间复杂度:O(n)

    创建一个大小为k的辅助数组tmp,先把nums的后nums.length - k个元素复制到tmp中,然后把nums的前k个元素挪到后面,最后把tmp中的元素复制到nums的起始位置。

    class Solution {
        public void rotate(int[] nums, int k) {
            if (nums.length == 0 || (k %= nums.length) == 0) return;
            int[] tmp = new int[k];
            System.arraycopy(nums, nums.length - k, tmp, 0, k);
            System.arraycopy(nums, 0, nums, k, nums.length - k);
            System.arraycopy(tmp, 0, nums, 0, k);
        }
    }

    真·解答一

    • 时间复杂度:O(n2)
    • 空间复杂度:O(1)

    每次向右移动1个位置,重复k次,就相当于向右移动k个位置。
    向右移动1个位置的时候先把最后的元素记录到t中,然后遍历数组nums把让nums[j] = nums[j - 1],最后把t放到nums[0]就完成了。

    class Solution {
        public void rotate(int[] nums, int k) {
            if (nums.length == 0 || (k %= nums.length) == 0) return;
            for (int i = 0; i < k; i++) {
                int t = nums[nums.length - 1];
                for (int j = nums.length - 1; j > 0; j--) {
                    nums[j] = nums[j - 1];
                }
                nums[0] = t;
            }
        }
    }

    真·解答二

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    通过不停地交换数组元素来实现。
    例如nums = [1, 2, 3, 4],k=2

    • 第一次交换:start = 0, i = 2, nums = [3, 2, 1, 4]
    • 第二次交换:start = 0 1, i = 0 3, nums = [3, 4, 1, 2]

    需要注意的是当i == start的时候需要把start移动到下一个位置,并且把i重置为start,否则的话会在nums.length % k == 0的那些元素那里循环,处理不到nums.length % k != 0 的那些元素。

    class Solution {
        public void rotate(int[] nums, int k) {
            if (nums.length == 0 || (k %= nums.length) == 0) return;
            int cnt = 0, start = 0, i = 0;
            while (cnt < nums.length) {
                i = (i + k) % nums.length;
                if (i == start)
                    i = ++start;
                else 
                    swap(nums, i, start);
                cnt++;
            }
        }
    
        private void swap(int[] a, int i, int j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    真·解答三

    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    采用翻转的方法,先翻转前nums.length - k个元素,在翻转后k个元素,最后翻转整个数组。
    例如nums = [1, 2, 3, 4, 5], k = 2

    • 第一次翻转:nums = [3, 2, 1, 4, 5]
    • 第二次翻转:nums = [3, 2, 1, 4, 5]
    • 第三次翻转:nums = [5, 4, 1, 2, 3]
    class Solution {
        public void rotate(int[] nums, int k) {
            if (nums.length == 0 || (k %= nums.length) == 0) return;
            reverse(nums, 0, nums.length - k - 1);
            reverse(nums, nums.length - k, nums.length - 1);
            reverse(nums, 0, nums.length - 1);
        }
    
        private void reverse(int[] a, int start, int end) {
            while (start < end) {
                int t = a[start];
                a[start++] = a[end];
                a[end--] = t; 
            }
        }
    }

    参考文章

    展开全文
  • Leetcode旋转数组

    2018-10-08 14:51:09
    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例 1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右...

    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    示例 1:

    输入: [1,2,3,4,5,6,7] 和 k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1 步: [7,1,2,3,4,5,6]
    向右旋转 2 步: [6,7,1,2,3,4,5]
    向右旋转 3 步: [5,6,7,1,2,3,4]

    示例 2:

    输入: [-1,-100,3,99] 和 k = 2
    输出: [3,99,-1,-100]
    解释:
    向右旋转 1 步: [99,-1,-100,3]
    向右旋转 2 步: [3,99,-1,-100]

    说明:
    尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    要求使用空间复杂度为 O(1) 的原地算法。

    这道题拿到手一个很直观的思路是我们能很快推出旋转后对应数的位置,比较简单的写法是利用一个O(N)的辅助数组来完成,而后复制该数组中的数到原数组中的值即可。
    后来想了下,感觉挖坑法也可以,但没实现,有兴趣的小伙伴可以去试试。

    这里想记录的其实是解法2
    我们随便拿个例子剖析一下:
    比如[1,2,3,4,5,6,7] 和 k = 3
    下面做3个操作:
    (1)将[0,n-k-1]范围内的数旋转一下,原数组变为[4,3,2,1,5,6,7];
    (2)将[n-k,n-1]范围内的数旋转一下,原数组变为[4,3,2,1,7,6,5];
    (3)整个数组翻转,原数组变为[5,6,7,1,2,3,4],正解
    按照这个思路可以写出如下代码,空间复杂度为O(1)

        public void rotate(int[] nums, int k) {
        	int len = nums.length;
        	k = k % len;//防止k大于数组长度引发边界问题
            reverse(nums,0,len-k-1);
            reverse(nums,len-k,len-1);
            reverse(nums,0,len-1);
        }
        
        public void reverse(int[] nums, int start, int end){
        	while(start<end){
        		nums[start] = nums[start]^nums[end];
        		nums[end] = nums[start]^nums[end];
        		nums[start] = nums[start]^nums[end];
        		start++;
        		end--;
        	}
        }
    

    题目本身不难,但这个解题的思路很值得学习。

    展开全文
  • leetcode 旋转数组的最小数字 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转...
  • LeetCode 旋转数组 系列

    多人点赞 热门讨论 2020-04-27 09:30:15
    旋转数组系列,多数是排序数组,然后进行旋转,可以使用二分查找。做一个集合,如还有缺失的,可以留言指出,一起加油! LeetCode 33. 搜索旋转排序数组(二分查找) LeetCode 81. 搜索旋转排序数组 II(二分查找) ...
  • otateArray(旋转数组)Rotateanarrayofnelementstotherightbyksteps.Forexample,withn=7andk=3,thearray[1,2,3,4,5,6,7]isrotatedto[5,6,7,1,2,3,4].Note:Trytocomeupasmanysolutions...
  • leetcode explore 初级算法第三题,旋转数组代码实现。原题链接:题目分析因为题目不是很长,这里把题目贴出来:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。示例 1:输入: [1,2,3,4,5,6,7] 和...
  • 寻找旋转数组的最小值II 均为二分查找 搜索旋转排序数组 class Solution: def search(self, nums: List[int], target: int) -> int: if not nums: return -1 n = len(nums) left, right = 0, n-1 # 将...
  • LeetCode 旋转数组通解

    2020-03-16 15:46:37
    遇到了第三题的旋转数组挺有意思。 不说了,直接看题: 看上就是数组的顺序调转,一开始楼主也不知道怎么做,就上网偷偷看了一眼答案,寻思我也看不懂什么翻转又什么数值变换的。 基础比较差的我看得一头雾水,...
  • 输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。 示例 1: 输入:[3,4,5,1,2] 输出:1 示例 2: 输入:[2,2,2,0,1] 输出:0 ...
  • 旋转数组系列总结 ———————————————— LeetCode 33. 搜索旋转排序数组(二分查找) LeetCode 81. 搜索旋转排序数组 II(二分查找) LeetCode 153. 寻找旋转排序数组中的最小值(二分查找) LeetCode ...
  • 解析旋转数组 由于该数组是升序排序,经过旋转后,最小值右边的数严格大于最小值,最大值左边的数严格小于最大值。 那么可以用二分查找的方法来解决这道题目,因为可以确定最小值一定在low和high之间,然后通过更新...
  • #leetcode 旋转数组

    2019-09-18 14:49:41
    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例 1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右...
  • LeetCode:逆转数组 探索初级算法 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例 1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6...
  • 题目: 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数 举例: 输入: [1,2,3,4,5...旋转第一步,保留原数组最后一个值,其余位置逐个向前推移 [1,2,3,4,5,6,7] ——>[1,2,3,4,5,6,6]——>[1,2,
  • 旋转数组 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例 1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步:[7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,403
精华内容 4,561
关键字:

leetcode旋转数组