系列文章目錄
文章目錄
- 系列文章目錄
- 前言
- 一、陣列中數字出現的次數
- 1.題目描述
- 2.解題思路
- 二、移除元素
- 1.題目描述
- 2.解題思路
- 三、洗掉有序陣列中重復項
- 1.題目描述
- 2.解題思路
- 總結
前言
一、陣列中數字出現的次數
陣列中數字出現的次數
1.題目描述
一個整型陣列 nums 里除兩個數字之外，其他數字都出現了兩次，請寫程式找出這兩個只出現一次的數字，要求時間復雜度是O(n)，空間復雜度是O(1)，
2.解題思路
- 先把陣列中所有的數異或一遍，相同數就會異或為0，不同的數會異或得到一個數，
- 找到這個數的結果中第j位為1，(一個int型有32位，任意找一位為1），
- 把j位為1的數分配為a組，j位為0的數分配為b組，相同的數要么在a組，要么在b組，
- 不同的數就會分配一個a組，一個b組，
- 再對a組、b組的數異或，相同的數被異或掉，剩下的就是結果數字，
代碼如下：
int* singleNumbers(int* nums, int numsSize, int* returnSize)
{
int x=0;
int y=0;
int ret=0;
int i=0;
for(i=0;i<numsSize;i++)
{
ret=ret^nums[i];
}
int j=0;
for(j=0;j<numsSize;j++)
{
if((ret>>j&1))
{
break;
}
}
int k=0;
for(k=0;k<numsSize;k++)
{
if(nums[k]>>j&1)
{
x=x^nums[k];
}
else
{
y=y^nums[k];
}
}
int* arr=(int*)malloc(sizeof(int)*2);
arr[0]=x;
arr[1]=y;
//把實參地址傳給形參，那么形參可以通過解參考改變實參
*returnSize=2;
return arr;
}
二、移除元素
移除元素
1.題目描述
給你一個陣列 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并回傳移除后陣列的新長度，不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入陣列，元素的順序可以改變，你不需要考慮陣列中超出新長度后面的元素
2.解題思路
- 第一種解法，把不是val的元素移動到新陣列中
代碼如下：
int RemoveElement(int *arr, int sz, int val) //把不是val的值存放到另一個陣列中
{
int i = 0;
int j = 0; //創建一個新陣列
for (i = 0; i < sz; i++)
{
if (arr[i] != val)
{
arr[j] = arr[i];
j++;
}
}
return j;
}
- 第二種解法兩個下標同時出發
代碼如下：
int RemoveElement(int* arr, int sz, int val) //兩個變數同時出發
{
int dest = 0;
int src = 0;
while (src < sz)
{
if (arr[src] == val)
{
src++;
}
else
{
arr[dest] = arr[src];
src++;
dest++;
}
}
return dest;
}
三、洗掉有序陣列中重復項
洗掉有序陣列中重復項
1.題目描述
給你一個有序陣列 nums ，請你 原地 洗掉重復出現的元素，使每個元素 只出現一次 ，回傳洗掉后陣列的新長度，不要使用額外的陣列空間，你必須在原地修改輸入陣列并在使用 O(1) 額外空間的條件下完成，
2.解題思路
- 定義三個下標dest=0、cur=0、next=1
- 判斷下標cur的值和下標next相等和不相等的情況
代碼如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int RemoveElement(int arr[], int sz)
{
if (sz == 0)
{
return 0;
}
int dest = 0;
int cur = 0;
int next = 1;
while (next < sz)
{
if (arr[cur] != arr[next])
{
arr[dest] = arr[cur];
dest++;
cur++;
next++;
}
else
{
while ( next<sz && arr[cur] == arr[next])
{
next++;
}
arr[dest] = arr[cur];
dest++;
cur = next;
next++;
}
}
if (cur < sz)
{
arr[dest] = arr[cur];
dest++;
}
return dest;
}
int main()
{
int arr[] = { 1, 1, 2, 3, 4, 5, 5, 6, 7 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret = RemoveElement(arr, sz);
printf("%d\n", ret);
return 0;
}
總結
以上就是今天要講的內容，本文僅僅簡單介紹了LeetCood中幾道陣列型別的題目，對我們以后是非常重要的，我們務必掌握！另外，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272787.html
標籤：其他
上一篇：單機游戲修改游戲資料（你自己就是一個外掛，看完這篇，你一定有不小的識訓）
下一篇：iOS之深入決議GCD的底層原理