1. 統計陣列中元素總結
1.1 統計元素出現的次數
為了統計元素出現的次數，我們肯定需要一個map來記錄每個陣列以及對應數字出現的頻次，這里map的選擇比較有講究：
- 如果資料的范圍有限制，如：只有小寫字母、1000以內的正數等，這時我們可以通過一個陣列來充當
map； - 如果資料的范圍沒有限制，或者資料范圍很大：如：
int的資料范圍，這時我們可以通過HashMap存盤對應的key和value；
可參考代碼：
for(int i = 0; i< nums.length; i++){
count[nums[i]]++;
}
1.2 ?統計元素在陣列中出現的最左和最右位置
首先想清楚一個問題：
- 從左到右遍歷，最后遍歷到的就是最右元素；
- 從右到左遍歷，最后遍歷到的就是最左元素；
我們就可以依據此，創建left和right變數，從左往右遍歷時更新right，從右往左遍歷時更新left，
for(int i = 0; i < nums.length; i++){
if(nums[i] == target){
right = i;
}
}
for(int i = nums.length - 1; i >= 0; i--){
if(nums[i] == target){
left = i;
}
}
1.3 ?統計元素有沒有出現(有沒有重復出現)
思路仍然是：統計元素出現的次數，最后根據count陣列來判斷元素是否出現或者元素是否重復出現，
有時，題目要求我們空間復雜度為O(1)，這時我們要仔細地審題，挖掘統計陣列與原陣列之間的關系，一般情況下我們只能通過修改原陣列來統計每個元素出現的次數，比如說：如果陣列中元素都在[1, n]之間，而且原陣列的長度也為：n，此時我們就可以通過修改原陣列來記錄元素出現的次數，
在這種型別的題目中，一個有用的觀念是：
- 對于
nums中的一個資料x，我們用nums[x - 1]來標識這個元素是否已經出現過； - 為了標識
nums[x - 1]是否出現過，我們不能使用nums中原來就會出現的數字，比如說：范圍[1, n]之間的數字；一個常用的方法是：將nums[x - 1]轉化為負數，這樣就可以用來標識x之前是否已經出現過；
for(int i = 0; i < nums.length; i++){
// 防止 x 為負數
int x = Math.abs(nums[i));
if(nums[x - 1] < 0){
// 出現過，做操作
}else{
// 通過負數來標識元素x已經出現過了
nums[x - 1] = - nums[x - 1];
}
}
2. 題目記錄
645. 錯誤的集合
分析題意
一個長度為n的集合s中本來存盤的是1-n的資料，將資料打亂后并挑選一個資料替換成1-n之間的其他資料，請你找出：被替換的資料和替換成的資料，
這道題的關鍵在于：資料其實是無序的，所以我們不能依靠相鄰元素的大小關系來進行判斷，
思路分析
如果我們能夠統計陣列中每個元素的出現次數，那么查到被替換的資料（頻次為0），替換成的資料（頻次為2）就十分的簡單，
int[] count = new int[nums.length];
for(int i = 0; i < nums.length; i++){
count[nums[i] - 1] ++;
}
for(int i = 0; i < count.length; i++){
if(count[i] == 0){
// 被替換的元素
}
if(count[i] == 2){
// 替換的元素
}
}
我們可以發現，count的大小為n，而nums的大小也為n，那么我們能不能用nums陣列來標識一個元素是否出現過呢？答案是可以的，
class Solution {
public int[] findErrorNums(int[] nums) {
int[] ans = new int[2];
for(int i = 0; i < nums.length; i++){
int k = Math.abs(nums[i]);
if(nums[k - 1] < 0){
// 前面已經出現過
ans[0] = k;
}else{
nums[k - 1] = - nums[k - 1];
}
}
// 經過上述程序
// 如果x出現，那么nums[x - 1] 為負數
// 如果x沒有出現，那么nums[x - 1]保持原樣不變
for(int i = 0; i < nums.length; i++){
if(nums[i] > 0){
ans[1] = i + 1;
break;
}
}
return ans;
}
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(1)
697. 陣列的度
分析題意
要想知道元素 從出現的最大頻次，那么我們需要統計每個元素出現的次數，
要計算長度就需要知道最大出現元素的起始位置和終止位置，即元素的最左位置和最右位置，
所以，這道題就轉化為了：求每個元素頻次以及最左和最右位置，
思路分析
由于資料的范圍較大，所以我們通過map來進行存盤，
class Solution {
public int findShortestSubArray(int[] nums) {
HashMap<Integer, Integer> count = new HashMap<>();
HashMap<Integer, Integer> left = new HashMap<>();
HashMap<Integer, Integer> right = new HashMap<>();
// 統計頻次和最右元素
for(int i = 0; i < nums.length; i++){
count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
right.put(nums[i], i);
}
// 統計最左元素
for(int i = nums.length - 1; i >= 0; i--){
left.put(nums[i], i);
}
int maxFreq = 0;
int minLen = 0;
for(Map.Entry<Integer, Integer> entry: count.entrySet()){
if(entry.getValue() > maxFreq){
maxFreq = entry.getValue();
minLen = right.get(entry.getKey()) - left.get(entry.getKey()) + 1;
}else if(entry.getValue() == maxFreq){
minLen = Math.min(minLen, right.get(entry.getKey()) - left.get(entry.getKey()) + 1);
}
}
return minLen;
}
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(n)
448. 找到所有陣列中消失的數字
分析題意
一個長度為n的陣列內，所有數字都在1-n范圍內，請找出在1-n范圍內但是沒有出現在陣列中的元素，
思路分析
如果我們知道1-n范圍內每個數字出現的頻次，那么出現頻次為0的所有元素都是我們想要找的元素，進一步來說，其實我們只關注這個元素是否出現過，即：>0 和 =0的差別，不關心具體出現了幾次，
題目要求我們使用常數空間復雜度來解決這道題目，那我們只能通過修改原陣列來實作統計是否元素是否出現這個需求，和上面一樣，我們使用 nums[x - 1]是否為負數來標識元素x是否已經出現過，
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for(int i = 0; i < nums.length; i++){
int k = Math.abs(nums[i]);
// 確保將 k-1 置為負數
nums[k - 1] = - Math.abs(nums[k - 1]);
}
List<Integer> ans = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
if(nums[i] > 0){
ans.add(i + 1);
}
}
return ans;
}
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(1), 回傳元素不計算
442. 陣列中重復的資料
分析題意
長度為n的陣列中，每個元素都在1-n范圍內，且每個元素要么出現1次，要么出現2次，（其實隱含著：1-n內的有些元素并不在陣列中，因為存在重復元素）找出所有出現2次的元素，
要求：時間復雜為O(n)，空間復雜度為O(1)
思路分析
如果我們能用一個集合存盤已經出現過的元素，然后每次遍歷一個新元素時先判斷該元素是否在已有的集合中：
- 如果已經存在那么它就是我們要找的重復元素，將該元素加入到結果集中；
- 如果不存在那么就把它加入到集合中；
for(int i = 0; i < nums.length; i++){
// 如果set中沒有該元素，添加成功回傳true
// 如果set中存在該元素，添加失敗回傳false
if(!set.add(nums[i]){
ans.add(nums[i]);
}
}
上述方法的時間復雜度為O(n)，但是空間復雜度也是O(n)，不符合要求，那么 我們是否有辦法降低時間復雜度呢？
由于陣列的長度是n，陣列中每一個數字都在1-n范圍內，所以我們可以用nums[x - 1] 來標識元素 x 的狀態：是否已經出現過，這樣我們就可以實作O(1)空間復雜度了，
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
int k = Math.abs(nums[i]);
if(nums[k - 1] < 0){
// 已經出現過，這一次是第二次出現
ans.add(k);
}else{
nums[k - 1] = - nums[k - 1];
}
}
return ans;
}
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(1)
41. 缺失的第一個正數
分析題意
給你一個未排序的整數陣列 nums ，請你找出其中沒有出現的最小的正整數，
請你實作時間復雜度為O(n)并且只使用常數級別額外空間的解決方案，
對于一個長度為n的陣列，其中沒有出現的最小正整數的范圍一定在：1~(n+1)范圍內，所以我們關注的資料只有1~(n+1)中每個數的出現頻次，
思路分析
題意中我們已經明白了：統計1~(n+1)中每個元素的出現頻次，其實我們只統計1~n就可以了，如果1~n都出現了，那么最小的正整數就是n+1，
統計1~n每個元素出現頻次，那么我們需要一個長度為n的陣列，這樣的話空間復雜度就是O(n)，不符合題意，那我們就只能從修改原陣列下手了，
還記得之前的題目，我們都是通過nums[x - 1]來標識元素x是否出現過，這道題依舊適用，但是要做一點點修改，因為我們需要用負數標識元素已經出現過，但是原陣列中的資料的范圍是 \([-2^{(31)}, 2^{31}-1]\)存在負數，所以我們需要先將超出1~n范圍內的陣列全部置為n+1 ，
class Solution {
public int firstMissingPositive(int[] nums) {
for(int i = 0; i < nums.length; i++){
if(nums[i] > nums.length || nums[i] <= 0){
nums[i] = nums.length + 1;
}
}
for(int i = 0; i < nums.length; i++){
int k = Math.abs(nums[i]);
if( k <= nums.length){
nums[k - 1] = - Math.abs(nums[k - 1]);
}
}
int ans = nums.length + 1;
for(int i = 0; i < nums.length; i++){
if(nums[i] >= 0){
ans = i+1;
break;
}
}
return ans;
}
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(1)
本文來自博客園，作者：睡覺不打呼，轉載請注明原文鏈接：https://www.cnblogs.com/404er/p/array_count.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509423.html
標籤：其他
上一篇：移動端滲透