資訊專(zhuān)欄INFORMATION COLUMN
摘要：求和相減是先求出到這個(gè)等差數(shù)列的和，再減去實(shí)際數(shù)組的和，就是缺失的數(shù)，第二種方法是，只要先按順序排列好，用二分法找到第一個(gè)和不相等的數(shù)就可以了。二分法求和相減法共個(gè)數(shù)，多加了一個(gè)異或法
Problem
Given an array contains N numbers of 0 .. N, find which number doesn"t exist in the array.
ExampleGiven N = 3 and the array [0, 1, 3], return 2.
Note找第一個(gè)缺失的數(shù)，可以用求和相減或二分法查找，也可以用位運(yùn)算XOR來(lái)做。
求和相減是先求出0到N這個(gè)等差數(shù)列的和，再減去實(shí)際數(shù)組的和，就是缺失的數(shù)，
第二種方法是，只要先按順序排列好[0, 1, 2, 3, 4, ...]，用二分法找到第一個(gè)和A[i]不相等的數(shù)i就可以了。
1. 二分法
public class Solution {
public int findMissing(int[] A) {
int len = A.length;
Arrays.sort(A);
int left = 0, right = len - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (A[mid] > mid) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return A[left] == left ? left + 1 : left;
}
}
2. 求和相減法
public class Solution {
public int findMissing(int[] A) {
int len = A.length;
int sum = 0;
for (int i = 0; i < len; i++) {
sum += A[i];
}
int targetsum = len * (len + 1) / 2; //0, 1, 2,...,len, 共len+1個(gè)數(shù)，多加了一個(gè)len
return targetsum - sum;
}
}
3. 異或法
public class Solution {
public int findMissing(int[] nums) {
int x = 0;
for (int i = 0; i <= nums.length; i++) {
x ^= i;
}
for (int i = 0; i < nums.length; i++) {
x ^= nums[i];
}
return x;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65628.html
Problem The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetit...
Problem Given two strings, you have to find the missing string. Example Given a string str1 = This is an exampleGiven another string str2 = is example Return [This, an] Solution public class Solution ...
摘要：找第一個(gè)缺失的正整數(shù)，只要先按順序排列好，也就是，找到第一個(gè)和不對(duì)應(yīng)的數(shù)就可以了。注意數(shù)組的從開(kāi)始，而正整數(shù)從開(kāi)始，所以重寫(xiě)排列的時(shí)候要注意換成，而就是從開(kāi)始的數(shù)組中的元素。 Problem Given an unsorted integer array, find the first missing positive integer. Example Given [1,2,0] re...
摘要：兩個(gè)循環(huán)遍歷整個(gè)矩陣，出現(xiàn)則將其周?chē)噜彽娜繕?biāo)記為，用子函數(shù)遞歸標(biāo)記。注意里每次遞歸都要判斷邊界。寫(xiě)一個(gè)的，寫(xiě)熟練。 Number of Islands Problem Given a boolean/char 2D matrix, find the number of islands. 0 is represented as the sea, 1 is represented as...
摘要：建立兩個(gè)堆，一個(gè)堆就是本身，也就是一個(gè)最小堆另一個(gè)要寫(xiě)一個(gè)，使之成為一個(gè)最大堆。我們把遍歷過(guò)的數(shù)組元素對(duì)半分到兩個(gè)堆里，更大的數(shù)放在最小堆，較小的數(shù)放在最大堆。同時(shí)，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...
閱讀 3134·2021-09-22 15:59
閱讀 1378·2021-08-30 09:46
閱讀 2353·2019-08-30 15:54
閱讀 2074·2019-08-26 12:15
閱讀 2607·2019-08-26 12:09
閱讀 1406·2019-08-26 11:57
閱讀 3395·2019-08-23 17:11
閱讀 1944·2019-08-23 15:59
