今日写题work

题目一：轮转数组

三种思路，时间复杂度越优越好

第一种思路: 直接暴力求解，空间复杂度为o(1),但时间复杂度为o(n^2)

#include <stdio.h>
void rotate(int* nums, int k, int len);
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	rotate(arr, 3, sizeof(arr) / sizeof(int));
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("%d ", arr[i]);
	}

}
void rotate(int* nums, int k, int len)
{
	if (k > len)
	{
		k %= len;
	}
	int i = 0, j = 0;
	for (i = 0; i < k; i++)
	{
		int tmp = nums[len - 1];
		for (j = len - 1; j > 0; j--)
		{
			nums[j] = nums[j - 1];
		}
		nums[j] = tmp;
	}
}

第二种思路: 调用库函数，时间复杂度o(n),但空间复杂度为o(n)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void rotate(int* nums, int k, int len);
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	rotate(arr, 3, sizeof(arr) / sizeof(int));
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("%d ", arr[i]);
	}

}
void rotate(int* nums, int k, int len)
{
	if (k > len)
	{
		k %= len;
	}
	int* tmp = (int*)malloc(sizeof(int) * len);
	if (tmp == NULL)
	{
		perror("malloc failed\n");
		return 1;
	}
	memcpy(tmp, nums + len - k, sizeof(int) * k);
	memcpy(tmp + k, nums, sizeof(int) * (len - k));
	memcpy(nums, tmp, sizeof(int) * len);

	free(tmp);
}

第三种思路: 翻转三次，时间复杂度0(n),空间复杂度o(1)，最优解

#include <stdio.h>
void rotate(int* nums, int k, int len);
void Reverse(int* arr, int left, int right);
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	rotate(arr, 3, sizeof(arr) / sizeof(int));
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("%d ", arr[i]);
	}

}
void Reverse(int* arr, int left, int right)
{
	while (left < right)
	{
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}
void rotate(int* nums, int k, int len)
{
	if (k > len)
	{
		k %= len;
	}
	Reverse(nums, 0, len - k - 1);
	Reverse(nums, len - k, len - 1);
	Reverse(nums, 0, len - 1);
}

题目二：消失的数字

两种思路，时间复杂度要求o(n)

第一种思路: 直接公式，求和（等差数列）

#include <stdio.h>
int missingNumber(int* nums, int numsSize);
int main()
{
	int arr[] = { 0,2,3 };
	int ret = missingNumber(arr, 3);
	printf("%d", ret);
	return 0;
}
int missingNumber(int* nums, int numsSize)
{
	int sum = (0 + numsSize) * (numsSize + 1) / 2;
	for (int i = 0; i < numsSize; i++)
	{
		sum -= nums[i];
	}
	return sum;
}

第二种思路: 异或（可参考往期博客单身狗）

#include <stdio.h>
int missingNumber(int* nums, int numsSize);
int main()
{
	int arr[] = { 0,2,3 };
	int ret = missingNumber(arr, 3);
	printf("%d", ret);
	return 0;
}
int missingNumber(int* nums, int numsSize) 
{
	int val = 0;
	for (int i = 0; i < numsSize; i++)
	{
		val ^= nums[i];
	}
	for (int i = 0; i <= numsSize; i++)
	{
		val ^= i;
	}
	return val;
}