- 從排序數(shù)組中刪除重復(fù)項(xiàng)
給定一個(gè)排序數(shù)組匠楚,你需要在原地刪除重復(fù)出現(xiàn)的元素画机,使得每個(gè)元素只出現(xiàn)一次盛卡,返回移除后數(shù)組的新長(zhǎng)度矗钟。
不要使用額外的數(shù)組空間唆香,你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
自己?jiǎn)栴}代碼(及正解):
PS:自己的問(wèn)題出在吨艇,沒(méi)有看清楚題目躬它,并且將賦值語(yǔ)句混亂為移動(dòng)。
細(xì)節(jié)在于i++處秸应,當(dāng)相等的時(shí)候i下標(biāo)先向后移動(dòng)虑凛,在進(jìn)行比較碑宴。
// 在一個(gè)數(shù)組中只能是賦值操作,不能修改長(zhǎng)度桑谍。 length是靜態(tài)常量
// 此方法為自己的方法延柠,只能用于統(tǒng)計(jì)不重復(fù)的個(gè)數(shù)
public static int removeDuplicates(int[] nums) {
int b = nums.length;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
b--;
}
}
return b;
}
*******正解********
public static int remove(int[] nums) {
if (nums.length == 0)
return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++; // 這一步很關(guān)鍵,請(qǐng)注意锣披。
nums[i] = nums[j];
System.out.println(nums[i]);
}
}
return i + 1;
}
2.旋轉(zhuǎn)數(shù)組
給定一個(gè)數(shù)組贞间,將數(shù)組中的元素向右移動(dòng)k 個(gè)位置,其中k 是非負(fù)數(shù)雹仿。
輸入:[1,2,3,4,5,6,7]和k= 3 輸出:[5,6,7,1,2,3,4]
解釋?zhuān)?/p>
向右旋轉(zhuǎn) 1 步:[7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步:[6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步:[5,6,7,1,2,3,4]
說(shuō)明:
盡可能想出更多的解決方案增热,至少有三種不同的方法可以解決這個(gè)問(wèn)題。
要求使用空間復(fù)雜度為 O(1) 的原地算法胧辽。
正解(自己結(jié)合網(wǎng)友的解法寫(xiě)的):
public static void rotate(int nums [] , int k ){
int len = nums.length;
if(len<=1) return;
int a [] = new int [len];
for(int i =0 ; i<len ; i++){
a[i] = nums[i];
}
k = k%len; //去重
for(int i = 0 ; i<len ; i++){
int s = k+i;
s = s %len;
nums [s] = a[i];
}
}
注:以下解法并沒(méi)有完全滿(mǎn)足題目要求
解法(一):
ps:在增加數(shù)組的操作上要注意:傳值引用問(wèn)題峻仇。 (使用了數(shù)組返回修改原引用)
public static int [] rotate1(int nums [] ,int k) {
int len = nums.length;
int a[] = new int[len];
for (int i = 0; i < len; i++) {
int s = k + i;
if (s >= len) {
s = s % len;
a[s] = nums[i];
}
a[s] = nums[i];
}
nums = a;
return nums;
}
解法(二):
ps:時(shí)間復(fù)雜度過(guò)高。
public static void rotate3(int[] nums, int k) {
int len = nums.length;
if (len > 1) {
for (int i = 0; i < k; i++) {
int temp = nums[0];
nums[0] = nums[len - 1];
for (int j = len - 1; j > 1; j--) {
nums[j] = nums[j - 1];
}
nums[1] = temp;
}
}
}
3.只出現(xiàn)一次的數(shù)字
給定一個(gè)非空整數(shù)數(shù)組邑商,除了某個(gè)元素只出現(xiàn)一次以外摄咆,其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素人断。
說(shuō)明:
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度吭从。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎?
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
使用Java語(yǔ)言恶迈,想了很久通過(guò)下標(biāo)來(lái)實(shí)現(xiàn)涩金,但是沒(méi)成功。在網(wǎng)上找到結(jié)果暇仲,利用異或來(lái)實(shí)現(xiàn)步做。細(xì)想一下這題主要考位運(yùn)算符中的 ^ (異或) 運(yùn)算符。 知識(shí)欠缺所致熔吗!
public int singleNumber(int[] nums) {
int res = 0 ;
for(int i = 0 ; i<nums.length ; i++){
res = res^nums[i] ;
}
return res;
}
轉(zhuǎn)載:位運(yùn)算符知識(shí)補(bǔ)充 .
https://blog.csdn.net/xiaopihaierletian/article/details/78162863
- 兩個(gè)數(shù)組的交集 II
給定兩個(gè)數(shù)組辆床,編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算它們的交集佳晶。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
思路:最開(kāi)始想到的是用最傳統(tǒng)的下標(biāo)來(lái)進(jìn)行解決桅狠,發(fā)現(xiàn)寫(xiě)出的代碼太過(guò)于復(fù)雜,可讀性很差轿秧,而且時(shí)間復(fù)雜度太高了中跌。
于是百度出正解。(對(duì)于Java中對(duì)于一些復(fù)雜數(shù)組的問(wèn)題菇篡,應(yīng)該結(jié)合類(lèi)集中的底層數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行求解會(huì)更好漩符。)
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> tmp = new ArrayList<>();
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0 ;i<nums1.length;i++){
Integer temp = map.get(nums1[i]);
map.put(nums1[i],(temp == null? 0:temp)+1);
}
for(int i=0;i<nums2.length;i++){
if(map.containsKey(nums2[i])&&map.get(nums2[i])!=0){
tmp.add(nums2[i]);
map.put(nums2[i],map.get(nums2[i])-1);
}
}
int[] result = new int[tmp.size()];
int i = 0;
for(Integer in : tmp){
result[i++] = in;
}
return result;
}
5.兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值,找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)驱还。
你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)一種答案嗜暴,且同樣的元素不能被重復(fù)利用凸克。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路:最開(kāi)始想的是將數(shù)組裝到集合中在進(jìn)行值的判斷,因?yàn)檫@樣可以將已經(jīng)獲得的元素進(jìn)行刪除闷沥,不用在寫(xiě)刪除元素的底層代碼萎战,也實(shí)現(xiàn)了,但是這樣的方式增加了時(shí)間復(fù)雜度舆逃。后來(lái)用數(shù)組就可以直接解決蚂维,雖然時(shí)間復(fù)雜度下降了,但是離標(biāo)準(zhǔn)還是偏高路狮。
public int [] twoSum(int [] nums , int target){
int result [] = new int [2];
for(int i = 0 ; i<nums.length ; i++){
for(int j = i+1 ; j<nums.length ; j++){
if(nums[i] + nums[j] == target){
result[0] = i;
result[1] = j;
break;
}
}
}
return result;
}