26.删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums
中唯一元素的个数。
考虑 nums
的唯一元素的数量为 k
,你需要做以下事情确保你的题解可以被通过:
- 更改数组
nums
,使nums
的前k
个元素包含唯一元素,并按照它们最初在nums
中出现的顺序排列。nums
的其余元素与nums
的大小不重要。 - 返回
k
。
java
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int k = 0; //新数组指针
for (int next = 0; next < n; next++) {
//不同则赋值
if (nums[k] != nums[next]) {
nums[++k] = nums[next];
}
}
return k + 1; //实际长度
}
}
80.删除有序数组中的重复项II
给你一个有序数组 nums
,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
双指针
java
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n <= 2) {
return n;
}
int slow = 2, fast = 2;
while (fast < n) {
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
}
169.多数元素
给定一个大小为 n
的数组 nums
,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋
的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
投机取巧版
java
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2]; // >= n/2 中间必定如此
}
}
投票
java
class Solution {
public int majorityElement(int[] nums) {
int x=0,votes=0;
for(int num:nums){ //增强for-each
if(votes == 0){
x = num;
}
votes += num==x ?1:-1;
}
return x;
}
}
189. 轮转数组
给定一个整数数组 nums
,将数组中的元素向右轮转 k
个位置,其中 k
是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]
解释: 向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
java
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
int[] arr = new int[n * 2]; //延长数组长度
System.arraycopy(nums, 0, arr, 0, n); //源数组、源数组的起始位置、目标数组、目标数组的起始位置以及要复制的元素个数
System.arraycopy(nums, 0, arr, n, n);
System.arraycopy(arr, n - k, nums, 0, n); //取回
}
}
121.买卖股票的最佳时机-贪心
给定一个数组 prices
,它的第 i
个元素 prices[i]
表示一支给定股票第 i
天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0
。
java
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for (int price : prices) {
cost = Math.min(cost, price);
profit = Math.max(profit, price - cost);
}
return profit;
}
}