旋转数组
给定一个数组，将数组中的元素向右移动 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]
方法一
// 性能较差劲
//void rotate(int* nums, int numsSize, int k) {
// int tem = 0;
// for (int i = 1; i <= k; i++) {
// tem = nums[numsSize - 1];
// for (int j = numsSize - 1; j >= 0; j--) {
// nums[j] = nums[j - 1];
// }
// nums[0] = tem;
// }
//}
方法二
// 执行用时 4ms 高效算法
void reverse(int *arr, int start, int end) {
int temp = 0;
while (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
void rotate(int* nums, int numsSize, int k) {
if (nums == NULL || numsSize == 0 || k % numsSize == 0) {
return;
}
int kcount = k % numsSize;
int middle = numsSize - kcount;
reverse(nums, 0, middle - 1); // reverse left part
reverse(nums, middle, numsSize - 1); // reverse right part
reverse(nums, 0, numsSize - 1); // reverse whole part
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int arr[] = {1,2,3,4,5,6,7};
rotate(arr, 7, 3);
for (int i = 0; i < 7; i++) {
printf("%d ",arr[i]);
}
printf("\n");
}
return 0;
}
这里有一个很巧妙的方法：
利用数组的length - k 把数组 分为两半；
reverse 左边和右边的数组；
reverse 总数组。
举一个例子：
1 2 3 4 5 6 7 如果k = 3 的话， 会变成 5 6 7 1 2 3 4
1 2 3 4 5 6 7 middle = 7 - 3 = 4，分为左边 4个数字，右边 3个数字
4 3 2 1 7 6 5 分别把左右reverse 一下
5 6 7 1 2 3 4 把总数组reverse 一下就会得到答案
参考文章：
http://www.cnblogs.com/grandyang/p/4298711.html
http://www.cnblogs.com/grandyang/p/4298711.html
