代码实现:
// 逆置数组 void nizhi_array(int *nums, int l, int r) { // 左闭右闭 if (l >= r) { return ; } for (int i = l, j = r; i < j; i++, j--) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } void rotate(int *nums, int numsSize, int k) { if (nums == NULL || k == 0 || numsSize == 1) { return ; } if (k > numsSize) { k %= numsSize; } nizhi_array(nums, 0, numsSize - 1); nizhi_array(nums, 0, k - 1); nizhi_array(nums, k, numsSize - 1); }
代码实现:把数组nums2元素添加在数组nums1元素后面,再冒泡排序
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int k = m; for (int i = 0; i < n; i++) { nums1[k++] = nums2[i]; } int flag = 1; // 标志位优化 当序列在找到所有的最大值之前就已经将序列排好序了,直接结束循环 for (int i = nums1Size - 1; i >= 1 && flag; i--) { // i决定了哪一轮冒泡 flag = 0; for (int j = 0; j < i; j++) { // j决定哪两个元素进行比较 if (nums1[j] > nums1[j + 1]) { flag = 1; int temp = nums1[j]; nums1[j] = nums1[j + 1]; nums1[j + 1] = temp; } } } }
代码实现:双指针
void moveZeroes(int *nums, int numsSize){ int l = 0; // 指向零 int r = 0; // 不指向零 while (r < numsSize) { if (nums[r] != 0) { int temp = nums[r]; nums[r] = nums[l]; nums[l] = temp; l++; } r++; } }
代码实现:
void duplicateZeros(int *arr, int arrSize) { for (int i = 0; i < arrSize; i++) { if (arr[i] == 0) { for (int j = arrSize - 1; j > i + 1; j--) { arr[j] = arr[j - 1]; } if (i < arrSize - 1) { arr[i + 1] = 0; } i += 1; } } }
代码实现:
int removeDuplicates(int* nums, int numsSize){ for (int i = 1; i < numsSize; i++) { if (nums[i] == nums[i - 1]) { for (int j = i; j < numsSize -1; j++) { nums[j] = nums[j + 1]; } i--; numsSize--; } } return numsSize; }
代码实现:
(1)单指针
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } void sortColors(int *nums, int numsSize) { int ptr = 0; for (int i = 0; i < numsSize; ++i) { // 先将数组中的0排好 if (nums[i] == 0) { swap(&nums[i], &nums[ptr]); ++ptr; } } for (int i = ptr; i < numsSize; ++i) { // 再将数组中的1排在0后面,剩下的全部都是2 if (nums[i] == 1) { swap(&nums[i], &nums[ptr]); ++ptr; } } }
(2)双指针
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } void sortColors(int *nums, int numsSize) { int p0 = 0, p1 = 0; for (int i = 0; i < numsSize; ++i) { if (nums[i] == 1) { swap(&nums[i], &nums[p1]); ++p1; } else if (nums[i] == 0) { swap(&nums[i], &nums[p0]); if (p0 < p1) { swap(&nums[i], &nums[p1]); } ++p0; ++p1; } } }
代码实现:
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* plusOne(int *digits, int digitsSize, int *returnSize) { for (int i = digitsSize - 1; i >= 0; i--) { if (digits[i] == 9) { digits[i] = 0; } else { digits[i]++; *returnSize = digitsSize; return digits; } } *returnSize = digitsSize + 1; int *ret = (int*)malloc(sizeof(int) * (digitsSize + 1)); memset(ret, 0, sizeof(int) * (digitsSize + 1)); ret[0] = 1; return ret; }
代码实现:投票法
因为多数元素在数组里出现的次数绝对大于n/2,所以用其他元素消去多数元素,剩下的必然是多数元素(两两抵消)int majorityElement(int *nums, int numsSize){ int a = nums[0]; // 投票对象 int flag = 1; // 票数 for (int i = 1; i < numsSize; i++) { // 遍历投票对象 if (a == nums[i]) { // 投票对象相同,票数+1 flag++; } else { // 投票对象不同,票数-1 flag--; if (flag < 0) { // 该元素不是多数元素,更新投票对象并把票数置1 a = nums[i]; flag = 1; } } } return a; }
代码实现:计数排序思想
int missingNumber(int *nums, int numsSize) { int arr[numsSize + 1]; memset(arr, 0, sizeof(arr)); int i; for (i = 0; i < numsSize; i++) { arr[nums[i]]++; } for (i = 0; i <= numsSize; i++) { if (arr[i] == 0) { break; } } return i; }