Love丶FFC's Blog

LintCode_easy:恢复旋转排序数组

2019-08-24 18:20:26
阅读：7539   •   评论：102
标签：,

描述

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

说明

什么是旋转数组？

比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

样例

Example1:

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

Example2:

[6,8,9,1,2] -> [1,2,6,8,9]

挑战

使用O(1)的额外空间和O(n)时间复杂度

编程语言：Java

解题思想：

1.因为数组从某个节点分开，左右两边都是有序的，所以首先使用比较大小的方法找到该节点的索引。

2.创建另外一个数组或泛型，承载右边的元素集合。

3.将左边的元素集合紧随其后进行覆盖。

时间复杂度：O(n)

IDE代码如下：

  1. package LintCode_Easy;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. public class _39 {
  7.  
  8. 	public static void main(String[] args) {
  9. 		/* 数组解法 */
  10. 		int[] nums = new int[] {6,8,9,1,2};		//初始化
  11. 		int[] changenums = new int[nums.length];	
  12. 		int minnum=nums[0];
  13. 		int minnumindex=0;
  14. 		for(int i=0;i<nums.length;i++)			//找到最小元素的索引
  15. 		{
  16. 			if(nums[i]<minnum)
  17. 			{
  18. 				minnum=nums[i];
  19. 				minnumindex=i;
  20. 			}
  21. 		}
  22. 		for(int i=minnumindex,j=0;i<nums.length;i++,j++)	//(索引-长度)的覆盖
  23. 		{
  24. 			changenums[j]=nums[i];
  25. 		}
  26. 		for(int i=0,j=nums.length-minnumindex;i<minnumindex;i++,j++)	//(0-索引)的覆盖
  27. 		{
  28. 			changenums[j]=nums[i];
  29. 		}
  30. 		nums=changenums;	//覆盖
  31. 		System.out.println(Arrays.toString(nums));
  32.  
  33.  
  34. 		/*泛型解法*/
  35. 		//泛型中的get方法用于其中指定位置的值,set方法用于赋给指定位置值
  36. 		List<Integer> nums = new ArrayList<Integer>();
  37. 		nums.add(5);
  38. 		nums.add(6);
  39. 		nums.add(1);
  40. 		nums.add(2);
  41. 		nums.add(3);
  42. 		nums.add(4);
  43. 		int minnum = nums.get(0);
  44. 		int minnumindex = 0;
  45. 		for(int i=0;i<nums.size();i++)
  46. 		{
  47. 			if(nums.get(i)<minnum)
  48. 			{
  49. 				minnum=nums.get(i);
  50. 				minnumindex=i;
  51. 			}
  52. 		}
  53. 		List<Integer> savenums = new ArrayList<Integer>();
  54. 		for(int i=0;i<minnumindex;i++)
  55. 		{
  56. 			savenums.add(nums.get(i));
  57. 		}
  58. 		for(int i=0,j=minnumindex;j<nums.size();i++,j++)
  59. 		{
  60. 			nums.set(i, nums.get(j));
  61. 		}
  62. 		for(int i=0,j=nums.size()-minnumindex;j<nums.size();i++,j++)
  63. 		{
  64. 			nums.set(j, savenums.get(i));
  65. 		}
  66. 		System.out.println(nums);
  67. 	}
  68.  
  69. }
  70.  

LintCode编辑器代码如下：

  1. public class Solution {
  2.     public void recoverRotatedSortedArray(List<Integer> nums) {
  3.         int minnum = nums.get(0);
  4. 		int minnumindex = 0;
  5. 		for(int i=0;i<nums.size();i++)
  6. 		{
  7. 			if(nums.get(i)<minnum)
  8. 			{
  9. 				minnum=nums.get(i);
  10. 				minnumindex=i;
  11. 			}
  12. 		}
  13. 		List<Integer> savenums = new ArrayList<Integer>();
  14. 		for(int i=0;i<minnumindex;i++)
  15. 		{
  16. 			savenums.add(nums.get(i));
  17. 		}
  18. 		for(int i=0,j=minnumindex;j<nums.size();i++,j++)
  19. 		{
  20. 			nums.set(i, nums.get(j));
  21. 		}
  22. 		for(int i=0,j=nums.size()-minnumindex;j<nums.size();i++,j++)
  23. 		{
  24. 			nums.set(j, savenums.get(i));
  25. 		}
  26.     }
  27. }

评论板

共有 102 条评论

  1. Gealpaste

    cheapest cialis generic online This systematic review aims to address these questions by examining the role of bacteria in low back pain and the relationship between bacteria and Modic change

    2023-05-08 08:30 回复

  2. intuido

    At this early point after induction, clusters of rGFP Cre NSCs were also located next to the rGFP Dcx neuroblasts Fig cheap levitra

    2023-06-13 09:32 回复

  3. JoeLit

    can you buy azithromycin over the counter in canada

    2023-07-07 13:03 回复

  4. CurtisHed

    voltaren gel discount

    2023-07-09 02:26 回复

  5. AshLit

    zoloft 50mg coupon

    2023-07-10 04:49 回复

  6. JoeLit

    lyrica 175 mg

    2023-07-19 11:14 回复

  7. DarrylBox

    tadalafil 20mg in india

    2023-08-05 23:52 回复

  8. JoeLit

    025 tretinoin

    2023-08-10 21:13 回复

  9. SueLit

    medicine prazosin 1 mg capsule

    2023-08-13 00:32 回复

  10. ZakLit

    best price cialis 20mg

    2023-08-13 05:28 回复

  11. DavisIgnip

    lipitor canada price

    2023-08-13 06:18 回复

  12. IvyLit

    express scripts com pharmacies

    2023-08-13 09:47 回复

  13. IvyLit

    atarax 25 mg over the counter

    2023-08-13 10:21 回复

  14. SamuelEcors

    legitimate canadian pharmacies

    2023-08-13 21:43 回复

  15. IvyLit

    canadian pharmacy no rx needed

    2023-08-13 21:52 回复

  16. Richardatone

    where to buy nolvadex 2018 uk

    2023-08-13 22:03 回复

  17. MaryLit

    phenergan over the counter usa

    2023-08-14 00:40 回复

  18. IvyLit

    online pharmacy no prescription

    2023-08-14 03:37 回复

  19. Michaelsmopy

    no script pharmacy

    2023-08-14 05:00 回复

  20. AshLit

    cost of brand name cymbalta

    2023-08-14 05:38 回复

  21. JoeLit

    nolvadex india

    2023-08-14 07:01 回复

  22. Richardatone

    baclofen 10 mg price

    2023-08-14 09:41 回复

  23. JackLit

    web pharmacy

    2023-08-14 12:52 回复

  24. Elwoodexcix

    triamterene 37.5

    2023-08-14 17:05 回复

  25. AlanLit

    prazosin 5 mg capsules

    2023-08-14 20:17 回复

  26. IvyLit

    cheapest pharmacy to fill prescriptions without insurance

    2023-08-15 01:29 回复

  27. JosephKip

    medicine prazosin tablets

    2023-08-15 01:51 回复

  28. JosephKip

    cost of cymbalta 30 mg

    2023-08-15 03:10 回复

  29. DarrylBox

    buy generic cialis with paypal

    2023-08-15 05:54 回复

  30. JackLit

    triamterene weight loss

    2023-08-15 08:00 回复

  31. EyeLit

    baclofen purchase

    2023-08-15 13:51 回复

  32. ZakLit

    drug levaquin

    2023-08-15 15:18 回复

  33. SamuelEcors

    real cialis online

    2023-08-15 18:33 回复

  34. Davidevelf

    best no prescription pharmacy

    2023-08-15 21:05 回复

  35. SamuelEcors

    order levaquin online

    2023-08-16 00:16 回复

  36. SueLit

    antibiotic levaquin

    2023-08-16 00:26 回复

  37. JosephKip

    metformin sr

    2023-08-16 06:09 回复

  38. Williamjotly

    tamoxifen arimidex

    2023-08-16 10:00 回复

  39. IvyLit

    tretinoin 0.1 gel coupon

    2023-08-16 12:42 回复

  40. SamuelEcors

    metformin buy online usa

    2023-08-16 16:26 回复

  41. Davidevelf

    robaxin 750 mg

    2023-08-16 22:29 回复

  42. Williamjotly

    atenolol for sale

    2023-08-16 22:56 回复

  43. AshLit

    endep 25 mg medication

    2023-08-17 07:35 回复

  44. ZakLit

    metformin 500 mg cost

    2023-08-17 11:02 回复

  45. IvyLit

    buying retin a online uk

    2023-08-17 12:36 回复

  46. Elwoodexcix

    how much is dexamethasone

    2023-08-17 20:35 回复

  47. Davidevelf

    atenolol 50 mg online

    2023-08-17 20:39 回复

  48. DavisIgnip

    prednisolone 5mg coupon

    2023-08-17 20:42 回复

  49. MaryLit

    where can i buy atarax in uk

    2023-08-18 04:07 回复

  50. DarrylBox

    phenergan vc

    2023-08-18 05:53 回复

  51. IvyLit

    cheap zithromax online

    2023-08-18 07:30 回复

  52. JosephKip

    pharmacy no prescription required

    2023-08-18 12:03 回复

  53. IvyLit

    buy nolvadex online india

    2023-08-18 12:26 回复

  54. DarrylBox

    cost of 30 baclofen

    2023-08-18 22:02 回复

  55. Elwoodexcix

    where can i buy retin a without prescription

    2023-08-18 23:57 回复

  56. Michaelsmopy

    synthroid 25 mcg cost

    2023-08-19 03:04 回复

  57. ZakLit

    retino 0.05 gel

    2023-08-19 03:16 回复

  58. JackLit

    can you buy phenergan over the counter

    2023-08-19 06:09 回复

  59. Michaelsmopy

    over the counter prednisone canada

    2023-08-19 08:25 回复

  60. ZakLit

    azithromycin tablets australia

    2023-08-19 09:02 回复

  61. Richardatone

    prednisone cost 10mg

    2023-08-19 13:30 回复

  62. CurtisHed

    generic lyrica cost

    2023-08-19 13:45 回复

  63. ZakLit

    finasteride online

    2023-08-19 15:13 回复

  64. SamLit

    prednisone prescription cost

    2023-08-19 16:45 回复

  65. EyeLit

    cortisol prednisone

    2023-08-19 17:17 回复

  66. SamuelEcors

    lisinopril 3.125

    2023-08-19 18:29 回复

  67. SamuelEcors

    cost of doxycycline in canada

    2023-08-19 20:10 回复

  68. Richardatone

    synthroid 200 mcg price

    2023-08-19 22:24 回复

  69. DavisIgnip

    quineprox 90 mg

    2023-08-19 23:04 回复

  70. Elwoodexcix

    doxycycline without rx

    2023-08-19 23:13 回复

  71. IvyLit

    retino 0.025 cream

    2023-08-20 01:48 回复

  72. IvyLit

    can i buy diflucan online

    2023-08-20 03:12 回复

  73. DarrylBox

    retino 0.025 gel

    2023-08-20 03:35 回复

  74. DarrylBox

    lyrica for sale

    2023-08-20 06:05 回复

  75. EyeLit

    plaquenil hives

    2023-08-20 07:55 回复

  76. SueLit

    doxycycline 20 mg capsules

    2023-08-20 08:06 回复

  77. EyeLit

    propecia for sale canada

    2023-08-20 09:28 回复

  78. AlanLit

    zestril over the counter

    2023-08-20 15:09 回复

  79. Davidevelf

    buy suhagra online usa

    2023-08-20 15:19 回复

  80. SamuelEcors

    canada drugstore pharmacy rx

    2023-08-20 16:12 回复

  81. IvyLit

    where can i buy prednisone

    2023-08-21 01:09 回复

  82. SamuelEcors

    strattera 60 mg

    2023-08-21 01:25 回复

  83. MaryLit

    suhagra tablet price india

    2023-08-21 09:00 回复

  84. Richardatone

    cheap zanaflex online

    2023-08-21 10:21 回复

  85. Elwoodexcix

    phenergan uk price

    2023-08-21 12:11 回复

  86. Elwoodexcix

    strattera 18 mg capsule

    2023-08-21 12:32 回复

  87. AshLit

    prednisone 15 mg daily

    2023-08-21 12:46 回复

  88. Elwoodexcix

    prinivil

    2023-08-21 19:14 回复

  89. SamLit

    diflucan 150 tablet

    2023-08-22 00:57 回复

  90. DarrylBox

    keflex cephalexin

    2023-08-22 02:03 回复

  91. IvyLit

    bactrim 800 160 mg

    2023-08-22 02:59 回复

  92. MaryLit

    celebrex 200mg for sale

    2023-08-22 06:37 回复

  93. SamuelEcors

    diflucan 200 mg capsule

    2023-08-22 10:58 回复

  94. SamLit

    bactrim cheap

    2023-08-22 15:04 回复

  95. ZakLit

    plavix generic india

    2023-08-22 17:28 回复

  96. JackLit

    amoxicillin where to get

    2023-08-22 19:54 回复

  97. JoeLit

    suhagra online india

    2023-08-22 19:58 回复

  98. Davidevelf

    synthroid 100 mcg

    2023-08-22 20:22 回复

  99. EyeLit

    retino cream

    2023-08-23 09:33 回复

  100. DarrylBox

    where to buy prednisone 5443 without prescription

    2023-08-23 09:48 回复

  101. SamLit

    synthroid 88 mg

    2023-08-23 14:20 回复

  102. AlanLit

    generic of augmentin

    2023-08-23 16:49 回复

--------查看该分类下最新文章--------
^
新版博客正在完善中！域名：http://www.loveffc:8080，点击跳转，完全移植后将去除端口号。

Copyright © 2018 - 2021 FFC的小站 - 滇 ICP 备 18010780 号 - 1

- Powered by WordPress & AliYun · Theme by FFC -

- Environment by Windows & XAMPP · Designed by WebStorm & VSCode -

已运行:

访问量：510752