- 03. 数组中重复的数字
- 04. 二维数组中的查找
- 11. 旋转数组的最小数字
- 21. 调整数组顺序使奇数位于偶数前面
- 39. 数组中出现次数超过一半的数字
- 42. 连续子数组的最大和
- 45. 把数组排成最小的数
- 56 - I. 数组中数字出现的次数
- 56 - II. 数组中数字出现的次数 II
- 66. 构建乘积数组
03. 数组中重复的数字
class Solution {
public int findRepeatNumber(int[] nums) {
int[] res = new int[nums.length];
for (int i : nums) {
res[i]++;
if (res[i] > 1) return i;
}
return -1;
}
}class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return nums[i];
}
}
return -1;
}
}class Solution {
public int findRepeatNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i : nums) {
if (!set.add(i)) {
return i;
}
}
return -1;
}
}04. 二维数组中的查找
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col] > target) {
col--;
} else if (matrix[row][col] < target) {
row++;
} else {
return true;
}
}
return false;
}
}11. 旋转数组的最小数字
class Solution {
public int minArray(int[] numbers) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int m = (i + j) / 2;
if (numbers[m] > numbers[j]) {
i = m + 1;
} else if (numbers[m] < numbers[j]) {
j = m;
} else {
j--;
}
}
return numbers[i];
}
}21. 调整数组顺序使奇数位于偶数前面
class Solution {
public int[] exchange(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] % 2 == 1 && nums[j] % 2 == 0) {
i++;
j--;
} else if (nums[i] % 2 == 1 && nums[j] % 2 == 1) {
i++;
} else if (nums[i] % 2 == 0 && nums[j] % 2 == 1) {
int temp = nums[i];
nums[i++] = nums[j];
nums[j--] = temp;
} else {
j--;
}
}
return nums;
}
}class Solution {
public int[] exchange(int[] nums) {
int i = 0, j = nums.length - 1, temp;
while (i < j) {
while (i < j && (nums[i] & 1) == 1) {
i++;
}
while (i < j && (nums[j] & 1) == 0) {
j--;
}
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return nums;
}
}39. 数组中出现次数超过一半的数字
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}class Solution {
public int majorityElement(int[] nums) {
int count = 0, result = 0;
for (int num : nums) {
if (count == 0) {
result = num;
}
count += (result == num) ? 1 : -1;
}
return result;
}
}42. 连续子数组的最大和
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int num : nums) {
if (sum <= 0) {
sum = num;
} else {
sum += num;
}
max = Math.max(max, sum);
}
return max;
}
}class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}45. 把数组排成最小的数
class Solution {
public String minNumber(int[] nums) {
String[] strings = getStringArray(nums);
Arrays.sort(strings, new Cop());
StringBuilder result = new StringBuilder();
for (String s : strings) {
result.append(s);
}
return result.toString();
}
private String[] getStringArray(int[] nums) {
String[] strings = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strings[i] = String.valueOf(nums[i]);
}
return strings;
}
class Cop implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
String s1 = o1 + o2;
String s2 = o2 + o1;
return s1.compareTo(s2);
}
}
}class Solution {
public String minNumber(int[] nums) {
String[] strings = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strings[i] = String.valueOf(nums[i]);
}
Arrays.sort(strings, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
StringBuilder result = new StringBuilder();
for (String s : strings) {
result.append(s);
}
return result.toString();
}
}56 - I. 数组中数字出现的次数
class Solution {
public int[] singleNumbers(int[] nums) {
int sum = 0;
for (int i : nums) {
sum = sum ^ i;
}
int flag = sum & (-sum);
int res = 0;
for (int i : nums) {
if ((flag & i) != 0) {
res = res ^ i;
}
}
return new int[]{res, sum ^ res};
}
}56 - II. 数组中数字出现的次数 II
class Solution {
public int singleNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i += 3) {
if (nums[i] != nums[i + 2]) {
return nums[i];
}
}
return nums[nums.length - 1];
}
}class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
int count = map.getOrDefault(i, 0);
map.put(i, count + 1);
}
for (Integer i : map.keySet()) {
if (map.get(i) == 1) {
return i;
}
}
return -1;
}
}class Solution {
public int singleNumber(int[] nums) {
int[] count = new int[32];
for (int i : nums) {
for (int j = 0; j < 32; j++) {
count[j] += i & 1;
i = i >>> 1;
}
}
int res = 0, flag = 3;
for (int i = 0; i < 32; i++) {
res += (1 << i) * (count[i] % flag);
}
return res;
}
}66. 构建乘积数组
class Solution {
public int[] constructArr(int[] a) {
int[] result = new int[a.length];
for (int i = 0, cur = 1; i < a.length; i++) {
result[i] = cur;
cur = cur * a[i];
}
for (int i = a.length - 1, cur = 1; i >= 0; i--) {
result[i] = result[i] * cur;
cur = cur * a[i];
}
return result;
}
}