• 算法的时间复杂度分析习题专题

    之前写了一篇重点是讲理论，今天重点在于对于题目的分析

    题目难度不分先后，有题目来源会直接给出链接或者位置

    第一题：消失的数字

    题目来源：LeetCode消失的数字

     分析

    第一种思路分析：

             参考代码：位置(chapter1/c++/disappear-number/lc_disappear_number1.cc)

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6.  
    7.  
    8. int find_disappear(int nums[], int len)
    9. {
    10. 	int res = -1;//保存结果，-1代表值没有被改变
    11. 	//先对数组进行排序
    12. 	sort(nums, nums + len);//需要两个参数,数组头指针与指针,但是这里不包括尾指针,所以指向数组越界的位置
    13. 	for (int i = 0; i < len; i++)
    14. 	{
    15. 		if (i != nums[i]) 
    16. 		{
    17. 			//这里直接缺少的就是i
    18. 			res = i;
    19. 		}
    20. 	}
    21. 	
    22. 	//这里就是没有匹配到的情况,就是最大的索引
    23. 	if (res ==  -1) 
    24. 	{
    25. 		res = len;
    26. 	}  
    27.  
    28. 	return res;
    29. }
    30.  
    31. int main()
    32. {
    33. 	int arr[] = {0, 1, 2};
    34. 	//这里长度要单独拿出来计算，因为arr传入到find函数里面，会直接当成一级指针来进行处理
    35. 	//指针一般也就是一般windows上4个字节，linux上八个字节来进行处理
    36. 	int len = sizeof(arr) / sizeof(arr[0]);
    37. 	int res = find_disappear(arr, len);
    38. 	printf("缺失的数字是:%d\n", res);
    39. 	return 0;
    40. }

    时间复杂度为O(nlogn)明显与题目要求不符合，no_pass

    下面是第二种思路分析

    参考代码：位置(chapter1/c++/disappear-number/lc_disappear_number2_pass.cc)

    1. #include 
    2.  
    3.  
    4. int find_number(int *nums, int len)
    5. {
    6. 	//正确的长度是
    7. 	int len_correct = len + 1;
    8. 	//计算正确求和值
    9. 	int sum_correct = (len_correct * (len_correct - 1)) / 2;
    10. 	int sum_wrong = 0;//非正确的求和值	
    11.  
    12. 	//开始轮替，计算非正确的值，然后相减
    13. 	for (int i = 0; i < len; i++)
    14. 	{
    15. 		sum_wrong += nums[i];//因为i本身就是从0开始的，所以用i来累加求和
    16. 	}
    17. 	
    18. 	return sum_correct - sum_wrong;
    19. }
    20.  
    21.  
    22. int main()
    23. {
    24. 	int arr[] = {0, 1, 3};
    25. 	int res = find_number(arr,3);
    26. 	printf("%d\n", res);
    27. 	return 0;
    28. }

    时间度O(n),通过

    下面是第三种思路分析：

     

    参考代码： 位置/chapter1/c++/disappear-number/lc_disappear_number3_pass.cc

    1. #include 
    2.   2 
    3.   3 
    4.   4 
    5.   5 int missing_number(int *nums, int len)
    6.   6 {
    7.   7         int res = 0;
    8.   8         for (int i = 0; i < len; i++)
    9.   9         {
    10.  10                 res ^= *(nums + i);
    11.  11                 res ^= i + 1;
    12.  12         }
    13.  13         return res;
    14.  14 }
    15.  15 
    16.  16 int main()
    17.  17 {
    18.  18         int nums[] = {0, 1};
    19.  19         int len = sizeof(nums) / sizeof(nums[0]);
    20.  20         int res = missing_number(nums, len);
    21.  21         printf("%d\n", res);
    22.  22         return 0;
    23.  23 }
    24. ~

    leetcode提交代码c++：

    参考代码：位置(/chapter1/c++/disappear-number/lc_accept.cc)

    1. class Solution {
    2. public:
    3.     int missingNumber(std::vector<int>& nums) {
    4.         int len_correct = nums.size() + 1;
    5.         int sum_correct = (len_correct * (len_correct - 1)) / 2;
    6.         int sum_wrong = 0;
    7.  
    8.         for (int i = 0; i < nums.size(); ++i) {
    9.             sum_wrong += nums[i];
    10.         }
    11.  
    12.         return sum_correct - sum_wrong;
    13.     }
    14. };

     

    java代码的实现

    java小知识点补讲：

    1.一个类中的静态方法在new一个非静态成员成员内部类的时候，成员内部类必须是static的  

    也就是说下面这种写法是错误的

    应该换成下面这种写法

     如果你实在想内部类不设置为static的，那么，也可以按照如下方式来做

    说一下原因：main是一个静态方法，也就是说它是先于对象而存在的，如果Solution是一个依赖于Lc对象才存在的对象，那么如果直接new Solution肯定是不行的，因为Lc这个类都没有被加载到内存里面来，也就是说，这个类在内存里面是没有空间的，Lc没有空间，那么它的内部类 Solution凭什么会有空间。另外说一句，类加载到方法区是不一定会去创建这个类的实例的，他只会把类的相关信息封存起来放到一个Class<相关类>的一个字节码对象里面

    说一下上面的类加载到方法区的机制

    参考代码：位置(/chapter1/java/disappear-number/Lc.java)

    1. public class Lc {
    2. 	
    3. 	static class Solution {
    4.  
    5. 		public int missingNumber(int[] nums) {
    6. 			//先求出正确的和
    7. 			int correct_len = nums.length + 1;
    8. 			int correct_sum = correct_len * (correct_len - 1) / 2;
    9. 			int wrong_sum = 0;//保留不正确的和
    10. 			
    11. 			for (int i = 0; i < nums.length; i++) {
    12. 				wrong_sum += nums[i];
    13. 			}
    14.  
    15. 			return correct_sum - wrong_sum;
    16. 						
    17. 		}
    18. 	}
    19.  
    20. 	
    21. 	public static void main(String []args) {
    22. 		int[] nums = {3, 0, 1};
    23. 		Solution solution = new Solution();
    24. 		int res = solution.missingNumber(nums);
    25. 		System.out.println(res);
    26. 	}
    27. }

    java第二种实现方式，采用异或的方式处理

    参考代码：位置（/chapter1/java/disappear-number/Lc1.java） 

    1. class Solution {
    2.   2         public int missingNumber(int[] nums) {
    3.   3                 //让所有数据异或
    4.   4                 int res = 0;//这用0来异或就是0与任何数异或都是0
    5.   5                 int len = nums.length;
    6.   6                 for (int i = 0; i < len; i++) {
    7.   7                         res ^= nums[i];//先异或原数组元素0  0 1 1 2
    8.   8                         res ^= i + 1;//正确数据
    9.   9                 }
    10.  10                 return res;
    11.  11         }
    12.  12 } 
    13.  13 
    14.  14         
    15.  15 public class Lc1 {
    16.  16         public static void main(String[] args) {
    17.  17                 int[] nums = {0, 1};
    18.  18                 Solution s = new Solution();
    19.  19                 int res = s.missingNumber(nums);
    20.  20                 System.out.println("缺失的值是:" + res);
    21.  21         }       
    22.  22 }

     上面代码自行提交，具体逻辑分析看上面c++代码分析，

    第二题：轮转数组

    题目来源：leetcode轮转数组 

    第一种思路：把整个数组变成一个循环链表来做

    针对于上面的情况，我们设计一个下面的链表来处理

    另外我需要说一下：链表不一定完全要采用分配内存，指针的方式的来做，可以用一个数组来模拟这样一种数据结构，下面看代码

    参考代码：chapter1/c++/rotate-array/lc_rotate_array1.cc

    1. #include 
    2.  
    3.  
    4. //定义存放数组下标的节点结构
    5. struct node 
    6. {
    7. 	int pos;//当前索引，我们需要打印的索引
    8. 	int next;//它指向的下一个结点的地址，我们需要靠它移动的索引
    9. };
    10.  
    11. void rotate_array(int *nums, int len, int k) 
    12. {
    13. 	//安全性检查
    14. 	//注意题目中的数组长度是给出了一个具体范围的
    15. 	if (nums == NULL || len < 1 || len > 100000 || k < 0 || k > 100000)
    16. 	{
    17. 		return;
    18. 	}
    19.  
    20. 	node arr[len];
    21.  
    22. 	//根据长度来初始化这个索引数组
    23. 	for (int i = 0; i < len; i++)
    24. 	{
    25. 		arr[i].pos = i;
    26. 		//最后一个下标的next要分开考虑，不能按照当前索引递增
    27. 		//它是指向索引0这个结点的
    28. 		if (i == len - 1) 
    29. 		{
    30. 			arr[i].next = 0;
    31. 		} else {
    32. 			arr[i].next = i + 1;
    33. 		}
    34. 	}
    35. 	
    36. 	//下面考虑k是几
    37. 	//我们要根据k来判定pos指针应该移动到哪一个结点
    38. 	//然后开时顺时针轮替打印
    39. 	//首先pos是指在数组最后一个索引位置，这是起始位置
    40. 	
    41. 	int index = len - 1;//数组中实际的索引长度,用它来控制数组索引的回减
    42. 	int pos = index;
    43. 	//i从1开始轮替的原因是如果k = 1，就不需要移动，已经指向了移动1次之后的标准打印位置
    44. 	for (int i = 1; i < k; i++)  
    45. 	{
    46. 		//考虑回减到pos = 0的情况，到达头之后
    47. 		//又要把链表指针指向了尾部
    48. 		if (pos == 0) 
    49. 		{
    50. 			//回到尾部，也就是最后一个结点
    51. 			pos = len - 1;
    52. 			index = len - 1;//index也回到最后一个位置，以便进行下一次轮替
    53. 		} else {
    54. 			//这里注意,不要使用index--
    55. 			//不然会先把index的值交给pos之后，然后在--
    56. 			pos = --index;
    57. 		}
    58. 	}
    59. 	
    60. 	//上面确定好了pos的位置，然后我们就可以顺时针打印了
    61. 	//打印肯定是数组的长度截止
    62. 	//按照给的格式打印，当然我们也可以把它放到一个新数组
    63. 	//然后返回打印
    64. 	printf("[");
    65. 	for (int i = 0; i < len; i++)//注意len在上面已经变成
    66. 	{
    67. 		if (i == len - 1) 
    68. 		{
    69. 			printf("%d]\n", nums[pos]);//注意打印原数组
    70. 		} else {
    71. 			printf("%d,", nums[pos]);
    72. 		}
    73. 		//pos按照数组中next往下面移动
    74. 		pos = arr[pos].next;
    75. 	}
    76. }
    77.  
    78. int main()
    79. {
    80. 	int arr[] = {1,2,3,4,5,6,7};
    81. 	int len = sizeof(arr) / sizeof(arr[0]);
    82. 	int k = 3;
    83. 	rotate_array(arr, len, k);
    84. 	return 0;
    85. }

    对上面的代码进行一个时间复杂度与空间复杂度的分析

    先来说一下时间复杂度

    综上所述时间复杂度是O(len + k + len),又因为我们在题目中对k与len 都是做了限制的，所以上面的k与len都可以看成一个常数，常数级别的算法时间复杂度就是O(1),但是我如果我们没有对上面的K与Len 进行一个限制，那么这两个数就不是常数，说是时间复杂度将是一个线性的，也就是O(n），注意这里是大O(1)

    下面来分析一下空间复杂度：

    然后其他空间都是常量级别的空间，也就是说不会随着输入的数据规模增加而增加，所以这里的空间复杂度就是O(n + 1),常数项忽略不计，空间复杂度就是O(n) 

    题目的进阶要我们时间复杂度是O(1)，很明显这里不太符合要求

    no pass

    第二种思路：还是把整个链表当成一个循环链表来看，只是我们对空间和时间上进行一些优化

    优化1：k的取值 

    所以上面我们对k的取值先做一些优化，减少循环的时间 k %= len

     优化2：额外开辟数组的空间优化

    针对于上面两种优化我们对代码做一些改进

     参考代码：/chapter1/c++/rotate-array/lc_rotate_array2.cc

    1. #include 
    2.  
    3. void rotate_array(int *nums, int len, int k)
    4. {
    5. 	//安全性检查
    6. 	//注意题目中的数组长度是给出了一个具体范围的
    7. 	if (nums == NULL || len < 1 || len > 100000 || k < 0 || k > 100000)
    8. 	{
    9. 		return;
    10. 	}
    11.  
    12. 	//一个额外空间的开辟
    13. 	int next[len];//直接保存下一个节点的索引
    14.  
    15. 	//初始化这片额外的空间
    16. 	for (int i = 0; i < len; i++) 
    17. 	{
    18. 		if (i == len - 1)
    19. 		{
    20. 			next[i] = 0;
    21. 		}
    22. 		else 
    23. 		{
    24. 			next[i] = i + 1;
    25. 		}	
    26. 	}
    27.  
    28. 	//下面对k的取值做一个优化
    29. 	k %= len;//限制Len的范围里面，毕竟在len之后，就要开始准备轮替了
    30. 	//但是我们确定我们pos的值之前，我们需要研究一下上面拿到的这样一个k
    31. 	//的取值是否是合理的取值
    32. 	//[1,2,3] 我们初始化的指针是指向了3这个位置，如果k=3,那么经过优化之后的k
    33. 	//就等于0,,也就是说明它需要回到一个起始状态，那我们需要移动这个指针，两次
    34. 	//回到1这个位置，因为pos这个位置是回减的，其余的当k= 1或者k=2都是合理
    35. 	//我上面假设的是len=3的时候的情况
    36. 	if (k == 0)
    37. 	{
    38. 		//k等于0的时候就说明
    39. 		//数组的所有状态全部走完，回到了起点
    40. 		k = len;
    41. 	}
    42. 	
    43. 	//下面开始确定pos的位置
    44. 	int index = len - 1;//中间轮替的变量，不改变len的取值
    45. 	int pos = index;//初始化到最后一个位置的指针
    46. 	for (int i = 1; i < k; i++)
    47. 	{
    48. 		if (pos == 0)
    49. 		{
    50. 			pos = len - 1;//回到我们设定的起始位置
    51. 		} else {
    52. 			pos = (--index);
    53. 		}
    54. 	}
    55. 	
    56. 	//上面pos就是指向了我们想要的位置
    57. 	//下面开始根据next打印值
    58. 	//这是一个用索引构造而成的循环链表
    59. 	printf("[");
    60. 	for (int j = 0; j < len; j++)
    61. 	{
    62. 		printf("%d",nums[pos]);
    63. 		if (j != len - 1)
    64. 		{
    65. 			printf(",");
    66. 		}
    67. 		pos = next[pos];
    68. 	}
    69. 	printf("]");
    70. }
    71.  
    72. int main()
    73. {
    74. 	int arr[] = {1,2,3,4,5,6,7};
    75. 	int len = sizeof(arr) / sizeof(arr[0]);
    76. 	int k = 3;
    77. 	rotate_array(arr, len, k);
    78. 	return 0;
    79. }
    80.

    下面还是来分析一下算法的时间复杂度与空间复杂度

     上面的算法时间复杂度就是：O(len + len + len)，由于len本身在题目中是一个常数，所以时间复杂度还是O(1),但是很明显上面的算法在某种情况下来说会快一些，比如我们在K值确定位置的一个轮询的过程中，如果k值设置到最大，len比较小的时候，只需要循环到len就可以了

    下面分析空间复杂度：

    空间复杂度没有改进。从微观层面来说，我们这个算法为每一个额外的数据节点都节省了四个字节大小的额外空间 ，但是由于有一个随着数据规模增大而增大的数组，所以，空间复杂度还是O(n)

    第三种思路：采用双向循环链表思想来优化一思路2的代码

    我们在做第二种思路的时候，也就是单向循环链表的时候，我们会发现其实有几个弊端

    比如下面：

     

    好了，下面直接上代码

    参考代码：/chapter1/c++/rotate-array/lc_rotate_array3.cc

    1. #include 
    2.  
    3.  
    4. void rotate_array(int *nums, int len, int k)
    5. {
    6. 	//安全性检查
    7. 	//注意题目中的数组长度是给出了一个具体范围的
    8. 	if (nums == NULL || len < 1 || len > 100000 || k < 0 || k > 100000)
    9. 	{
    10. 		return;
    11. 	}
    12. 	
    13. 	
    14. 	int next[len];
    15. 	//初始化双向链表数组
    16. 	for (int i = 0; i < len; i++)
    17. 	{
    18. 		//反向循环，在数组里面我们就可以了控制，所以但是单数只需要一个next数组就可以了
    19. 		if (i == len - 1)
    20. 		{
    21. 			next[i] = 0;
    22. 		} else {
    23. 			next[i] = i + 1;
    24. 		}
    25. 	}
    26.  
    27. 	//优化k的值，计算pos的位置
    28. 	k %= len;//len = 3[0,1,2];//0就代表回到了链表的起点
    29. 	
    30. 	int pos = 0;//这里我们可以直接把pos放在第一个结点
    31. 	//这里指针需要逆时针移动，所以不用怕
    32. 	int index = len;
    33. 	for (int i = 0; i < k; i++)
    34. 	{
    35. 		pos = --index;//比如k = 1的时候就移动到k = 2的位置，k = 2,就会移动到1的位置
    36. 		if (pos == 0)
    37. 		{
    38. 			index = len;//如果回到起始位置，在往下面循环，就要从最后一个位置
    39. 			//但是这里也不用不限定，上面只会在当前数组里面循环一圈结束，这是k决定的
    40. 		} 
    41. 	}
    42.  
    43. 	//上面就是逆时针移动了指针
    44. 	//下面我们顺时针打印出来
    45. 	printf("[");
    46. 	for (int i = 0; i < len; i++)
    47. 	{
    48. 		printf("%d", nums[pos]);
    49. 		if (i != len - 1)
    50. 		{
    51. 			printf(",");
    52. 		}
    53. 		pos = next[pos];
    54. 	}
    55. 	printf("]");
    56. }
    57.  
    58. int main()
    59. {
    60. 	int arr[] = {1,2,3,4,5,6,7};
    61. 	int len = sizeof(arr) / sizeof(arr[0]);
    62. 	int k = 3;
    63. 	rotate_array(arr, len, k);
    64. 	return 0;
    65. }
    66.  
    67.  
    68.

    算法时间复杂度与空间复杂度与上面一样，这个位置就不做过多的阐述

    第四种思路：直接采用暴力破解的方法，双备份循环的方法来做

    下面是思路分析

    参考代码：位置（chapter1/c++/rotate-array/lc_rotate_array4.cc）

    1. #include 
    2.  
    3.  
    4. void rotate_array(int *nums, int len, int k)
    5. {
    6. 	//安全性检查
    7. 	//注意题目中的数组长度是给出了一个具体范围的
    8. 	if (nums == NULL || len < 1 || len > 100000 || k < 0 || k > 100000)
    9. 	{
    10. 		return;
    11. 	}
    12. 	
    13. 	//还是把k进行优化一下
    14. 	k %= len;//限制在数组长度范围之内
    15. 	int bak_cur;//赋值给j+1的结点值
    16. 	int bak_next;//j+1的备份
    17. 	//整体循环移动
    18. 	for (int i = 0; i < k;i++)
    19. 	{
    20. 		//初始化bak_cur与bak_next
    21. 		//这里bak_next初始化什么都无所谓
    22. 		//主要是需要初始化bak_cur,因为我们要用bak_cur初始化j+1这样一个位置
    23. 		bak_cur = nums[0];//每次内部数组循环完之后都会回到索引为0的位置开始移动
    24. 		bak_next = 0;//这里给个初始值就可以了
    25. 		//开始每一次内部的数组循环移动
    26. 		for (int j = 0; j < len; j++)
    27. 		{
    28. 			//这里最后一个节点需要特殊考虑
    29. 			//因为它的下一个节点又回到了索引为0的节点
    30. 			//并且它的备份已经在它之前一个位置就备份好了
    31. 			//我们也不需要去修改bak_next这个备份值
    32. 			if (j == len - 1) 
    33. 			{
    34. 				nums[0] = bak_cur;//直接给备份结点值就可以了
    35. 				//然后开始下一次k的轮替
    36. 			} else {
    37. 				//先来备份j+1
    38. 				bak_next = nums[j+1];
    39. 				//在去改变j+1;
    40. 				nums[j+1] = bak_cur;//用上一个节点的备份去改变
    41. 				bak_cur = bak_next;//在把上一个节点的备份值给改变一下
    42. 			}
    43. 		}
    44. 	}
    45.  
    46. 	//打印
    47. 	printf("[");
    48. 	for (int n = 0; n < len; n++)
    49. 	{
    50. 		printf("%d", nums[n]);//已经是移动完了之后的数组了
    51. 		if (n != len - 1)
    52. 		{
    53. 			printf(",");
    54. 		}
    55. 	}
    56. 	printf("]");
    57. }
    58.  
    59. int main()
    60. {
    61. 	int arr[] = {1,2,3,4,5,6,7};
    62. 	int len = sizeof(arr) / sizeof(arr[0]);
    63. 	int k = 3;
    64. 	rotate_array(arr, len, k);
    65. 	return 0;
    66. }
    67.

    算法时间复杂度与空间复杂度分析

    时间复杂度：

    虽然题目限定了数据大小，可以看成一个常量级别的算法时间复杂度，但是这里采用了双层for循环，时间复杂度直接拉满，虽然题目没有规定时间复杂度，但是这个算法也不用考虑

    空间复杂度：

    整体的算法我们没有随着数据的规模增大而新开辟一个数组，全是常量级别的空间，所以，这里的空间复杂度都是O(1) ，如果只考虑空间复杂度来说，这个题目可以算pass，通过
     

    第五种思路：直接根据每一个结点移动k次之后，算出它相应的被赋值结点的位置索引

    这个题目我们简单思考一下：

    它是有规律性的，比如k值，它总会在循环k次之后，又重新回到初始状态，所以我们可以直接限定k的取值，那么又在考虑每一个结点变化之后的位置，其实也是一个规模性，比如下面这个

    参考代码： 位置（chapter1/c++/rotate-array/lc_rotate_array5.cc）

    1. #include 
    2.  
    3.  
    4. void rotate_array(int *nums, int len, int k)
    5. {
    6. 	//做一些安全性判断
    7. 	if (nums == NULL || len < 1 || len > 100000 || k < 0 || k > 100000)
    8. 	{
    9. 		return;
    10. 	}
    11. 	//重新定位k的值
    12. 	//k的值决定了数组形态
    13. 	//每次到达k=len的时候，又会开始轮替
    14. 	//也就是说数组会回到新的起始位置
    15. 	//对于这样一个循环的找位置的数组来说
    16. 	//采用%len长度，直接限定了它的范围
    17. 	//所有k轮替全都可以放在len这个范围里面
    18. 	k %= len;//假如len = 3,k的取值[0,1,2]0代表不动，1代表1次，2代表2次
    19. 	
    20.  
    21. 	//k决数组形态，那么数组最终移动之后的形态确定了
    22. 	//下面开启式确定每一个位置，被哪一个位置所替代
    23. 	//注意上面的操作都是在一个数组里面操作，只是找相对位置
    24. 	printf("[");
    25. 	for (int i = 0; i < len; i++) 
    26. 	{
    27. 		//计算新位置
    28. 		//新位置就是数组会被替换的位置
    29. 		//拿到替换位置，也就是拿到了这个位置应该有的值
    30. 		//这个位置计算的分析看文章部分
    31. 		int new_pos = (i + len - k) % len;
    32. 		printf("%d", nums[new_pos]);
    33. 		if (i < len - 1) 
    34. 		{
    35. 			printf(",");
    36. 		}
    37. 	}
    38. 	printf("]\n");
    39. }
    40.  
    41.  
    42. int main()
    43. {
    44. 	int arr[] = {1,2,3,4,5,6,7};
    45. 	int len = sizeof(arr) / sizeof(arr[0]);
    46. 	int k = 3;
    47. 	rotate_array(arr, len, k);
    48. 	return 0;
    49. }

    算法时间复杂度分析：

    这里几乎完美，没有任何的数据移

    空间复杂度分析：

    O(1) 没有任何任何随着数据规模增大而开辟的空间，完美通过pass

    下面是Java代码的实现 

     下面这个没有位置，因为不可提交，所以这里仅仅是看一下分析思路，因为java里面的代码代码全部都是提交版本，所以这里不做过多说明

    1. #include 
    2.  
    3.  
    4. void rotate_array(int *nums, int len, int k)
    5. {
    6. 	//做一些安全性判断
    7. 	if (nums == NULL || len < 1 || len > 100000 || k < 0 || k > 100000)
    8. 	{
    9. 		return;
    10. 	}
    11. 	//重新定位k的值
    12. 	//k的值决定了数组形态
    13. 	//每次到达k=len的时候，又会开始轮替
    14. 	//也就是说数组会回到新的起始位置
    15. 	//对于这样一个循环的找位置的数组来说
    16. 	//采用%len长度，直接限定了它的范围
    17. 	//所有k轮替全都可以放在len这个范围里面
    18. 	k %= len;//假如len = 3,k的取值[0,1,2]0代表不动，1代表1次，2代表2次
    19. 	
    20.  
    21. 	//k决数组形态，那么数组最终移动之后的形态确定了
    22. 	//下面开启式确定每一个位置，被哪一个位置所替代
    23. 	//注意上面的操作都是在一个数组里面操作，只是找相对位置
    24. 	printf("[");
    25. 	for (int i = 0; i < len; i++) 
    26. 	{
    27. 		//计算新位置
    28. 		//新位置就是数组会被替换的位置
    29. 		//拿到替换位置，也就是拿到了这个位置应该有的值
    30. 		//这个位置计算的分析看文章部分
    31. 		int new_pos = (i + len - k) % len;
    32. 		printf("%d", nums[new_pos]);
    33. 		if (i < len - 1) 
    34. 		{
    35. 			printf(",");
    36. 		}
    37. 	}
    38. 	printf("]\n");
    39. }
    40.  
    41.  
    42. int main()
    43. {
    44. 	int arr[] = {1,2,3,4,5,6,7};
    45. 	int len = sizeof(arr) / sizeof(arr[0]);
    46. 	int k = 3;
    47. 	rotate_array(arr, len, k);
    48. 	return 0;
    49. }

    写到这的时候我发现我理解错了题目的意思，这个题目的意思是，需要在函数内部，把这个数组给改变了，所以上面思路的提交代码全都不可用，不过也很好解决，每一种除了第四种思路之外，每一种思路你都弄一个新数组，然后把找到的相应的值放进去就行了，不过全部代码的空间复杂度就会特别大。对于第四种暴力破解，虽然满足了空间上的O(1)开销但是耗费的时间确是非常大，也不建议使用

    下面是第四种方法的java代码实现，不提供位置，仅供参考

    1. import java.util.Arrays;
    2.  
    3. class Solution {
    4. 	public void rotate(int []nums, int k) {
    5. 		if (nums == null || nums.length < 1 || nums.length > 100000 || 
    6. 		k < 0 || k > 100000) {
    7. 			return;
    8. 		}
    9.  
    10. 		int len = nums.length;
    11. 		//优化k
    12. 		k %= len;
    13. 		//采用双备份的方法来做
    14. 		int bak_cur;//给下一个j+1赋值
    15. 		int bak_next;//j+1的备份
    16. 		for (int i = 0; i < k; i++)
    17. 		{
    18. 			//没走完一次内部循环，又会回到数组开头的位置
    19. 			bak_cur = nums[0];//这里永远初始化第一个结点的值
    20. 			bak_next = 0;//这里初始化什么目前来说无所谓
    21. 			for (int j = 0; j < len; j++)
    22. 			{
    23. 				//分尾结点来考虑
    24. 				if (j != len - 1) {
    25. 					//先来备份j+1
    26. 					bak_next = nums[j + 1];
    27. 					//赋值
    28. 					nums[j + 1] = bak_cur;
    29. 					//改变备份当前结点
    30. 					bak_cur = bak_next;
    31. 				} else {
    32. 					//直接把最后一个结点
    33. 					//就要去改变第一个结点
    34. 					//然后又回到开始的循环里面
    35. 					nums[0] = bak_cur;
    36. 				}
    37. 			}
    38. 		}
    39. 	}
    40. }
    41.  
    42. public class Lc {
    43. 	public static void main(String []args) {
    44. 		Solution s = new Solution();
    45. 		int []nums = {1,2,3,4,5,6,7};
    46. 		int k = 3;
    47. 		s.rotate(nums, k);
    48. 		System.out.println(Arrays.toString(nums));
    49. 	}
    50. }
    51.  
    52.

    上面代码可以提交一下，肯定会超时

    好了我们不得不在想一种思路

    第六种思路：考虑采用反转的思想来做 

    首先这个数组的整体移动呈现一个规律性，比如前k个结点往后，后面len - k个结点往前，只是针对于不同的k值，数组最终呈现不同的形态，因此我们可以这样理解，每一个k值都会有一个反转的规律，我们把这个规律记下来就行，举个实际例子来说

    参考代码：位置（/chapter1/java/rotate-array/Lc.java） 

    1. import java.util.Arrays;
    2.  
    3. class Solution {
    4.  
    5.  
    6. 	void rotate(int []nums, int k) {
    7. 		if (nums == null || nums.length < 1 || nums.length > 100000 || 
    8. 		k < 0 || k > 100000) {
    9. 			return;
    10. 		}
    11. 		
    12. 		int len = nums.length;
    13. 		//还是把k值进行优化
    14. 		k %= len;
    15. 		//先来反转整体数组
    16. 		reverse(nums, 0, len - 1);
    17. 		//旋转后面前移，旋转前k个元素
    18. 		reverse(nums, 0, k - 1);
    19. 		//前面的往后移，旋转后买那len - k个元素
    20. 		reverse(nums, k, len - 1);
    21. 	}
    22. 	
    23.  
    24. 	//先来写一个反转工具
    25. 	void reverse(int []nums, int start, int end) {
    26. 		while(start < end) {
    27. 			//这里面就是值的交换
    28. 			int temp = nums[start];
    29. 			nums[start] = nums[end];
    30. 			nums[end] = temp;
    31. 			start++;
    32. 			end--;
    33. 		}
    34. 	}
    35. }
    36.  
    37.  
    38. public class Lc {
    39. 	public static void main(String []args) {
    40. 		Solution s = new Solution();
    41. 		int []nums = {1,2,3,4,5,6,7};
    42. 		int k = 3;
    43. 		s.rotate(nums, k);
    44. 		System.out.println(Arrays.toString(nums));
    45. 	}
    46. }
    47.  
    48.

     直接上面的提交代码就行。

    c++版本的代码提交 

    参考代码：位置（chapter1/c++/rotate-array/lc_accept.cc） 

    1. #include 
    2. #include 
    3. #include  // 包含 reverse 函数的头文件
    4.  
    5. using namespace std;
    6.  
    7. class Solution {
    8. public:
    9.     void rotate(vector<int>& nums, int k) {
    10.         if (nums.empty() || k < 0 || k > 100000) {
    11.             return;
    12.         }
    13.         
    14.         int len = nums.size();
    15.         // 优化 k 的取值
    16.         k %= len;
    17.         
    18.         // 反转整个数组
    19.         reverse(nums.begin(), nums.end());
    20.         // 反转前 k 个元素
    21.         reverse(nums.begin(), nums.begin() + k);
    22.         // 反转剩余的元素
    23.         reverse(nums.begin() + k, nums.end());
    24.     }
    25. };
    26.  
    27. int main() {
    28.     Solution s;
    29.     vector<int> nums = {1, 2};
    30.     int k = 3;
    31.     s.rotate(nums, k);
    32.     
    33.     // 输出旋转后的数组
    34.     for (int num : nums) {
    35.         cout << num << " ";
    36.     }
    37.     cout << endl;
    38.     
    39.     return 0;
    40. }

    好了，说到这，算法时间复杂度O(n),空间复杂度O(1) 

  • 相关阅读:
    使用 Neuron 接入 Modbus TCP 及 Modbus RTU 协议设备
    MySQL-0-概述-介绍和安装以及MySQL数据模型
    MATLAB算法实战应用案例精讲-【图像处理】机器视觉
    英伟达AI布局的新动向：H200 GPU开启生成式AI的新纪元
    ThreadPoolExecutor详解
    内中断（一）
    文件下载js实现
    Hadoop虚拟化的性能对比和调优经验
    大模型LLM深入浅出、主打通俗易懂
    【Shell脚本12】Shell 输入/输出重定向
  • 原文地址：https://blog.csdn.net/Pxx520Tangtian/article/details/133417813