1.Sum of the array numbers
int sum(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
result += nums[i];
}
return result;
}
2.Minimum element of the array
int minimum(int a , int b) {
if (a < b) {
return a;
}
return b;
}
int minimum(int[] nums) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < min) {
min = nums[i];
}
}
return min;
}
3.Second minimum element of the array
int secondMinimum(int[] nums) {
int min = Math.min(nums[0],nums[1]);
int secondMin = Math.max(nums[0],nums[1]);
for (int i = 2; i < nums.length; i++) {
if (nums[i] < min) {
secondMin = min;
min = nums[i];
} else if (nums[i] == min) {
secondMin = min;
} else if (nums[i] > min && nums[i] < secondMin) {
secondMin = nums[i];
} else if (nums[i] == secondMin) {
continue;
} else {
continue;
}
}
return secondMin;
}
4.Reverse Array
//双指针，前后交换
public void reverseArray(int[] nums) {
int first = 0, end = nums.length - 1;
while (first < end) {
swap(nums,first++,end--);
}
}
private void swap(int[] nums, int first, int second) {
//注意这里的first和second和上面的区别，不同的函数
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
5.Odd Even Sort
奇数在前，偶数在后
public void oddEvenSort(int[] nums) {
int first = 0, second = nums.length-1;
while (first < second) {
while (first < second && nums[fisrt] % 2 == 1) {
first++;//如果是奇数就跳过继续往下遍历&每次都判断first < second防止越界
}
while (first < second && nums[second] % 2 == 0) {
second--;
}
if (first < second) {
swap(nums,first++,second--);
}
}
}
6.Pivot Sort
找出一个数，左边的数都比他小，右边的都比他大
public void pivotSort(int[] nums, int pivot) {
int first = 0, second = nums.length - 1;
while (first < second && nums[first] <= pivot) {
first++;
}
while (first < second && nums[second] > pivot) {
second--;
}
if (first < second) {
swap(nums,first++,second--);
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
7.Remove Element
前后指针，把要删除的元素放在最后。first指针从左边开始数，不相等就跳过，相等就和右边不等于目标值的元素交换
public int removeElement(int[] nums, int val) {
if (nums.length == 0) {
return 0;
}
int first = 0, second = nums.length - 1;
while (first < second) {
while (first < second && nums[first] != val) {
first++;
}
while (first < second && nums[second] == val) {
//等于目标值就放在最后
second--;
}
if (first < second) {
swap(nums,first++,second--);
}
}
return return nums[first] != val ? first+1 : first;//例子[3,2,2,3]删掉3，考虑first等于second
}
//Solution2 for remvoe element
public int removeElement(int[] nums, int val) {
int index = 0, len = nums.length;
//len is the valid length of remaining array
while (index < len) {
if (nums[index] == val) {
len--;//remove one element
//Keep the possible valid element
nums[index] = nums[len];
} else {
index++;
}
}
return len;
}
8.Merge Two Sorted Array
//粗暴的做法，两个数组，两个指针分别指向数组的头地址，小的放入新的数组里，然后最后再把result的数压到nums1里。需要额外空间。这道题注意是把nums2压入nums1，而不是生成一个新的数组
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] result = new int[m + n];
int i = 0, j = 0, index = 0;
while (i < m && j < n) {
if (nums1[i] < nums2[j]) {
result[index++] = nums1[i++];
} else {
result[index++] = nums2[j++];
}
}
while (i < m) {
result[index++] = nums1[i++];
}
while (j < n) {
result[index++] = nums2[j++];
}
for (i = 0; i < m + n; i++) {
nums1[i] = result[i];
}
}
}
solution:归并排序，分而治之
class Solution:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
result = []
left, right = 0, 0
while left < m and right < n:
if nums1[left] < nums2[right]:
result.append(nums1[left])
left += 1
else:
result.append(nums2[right])
right += 1
#比较完以后肯定有一个数组没有出完
while left < m:
result.append(nums1[left])
left += 1
while right < n:
result.append(nums2[right])
right += 1
for i in range(m + n):
nums1[i] = result[i]
引申：[Sort Integer II]http://www lintcode.com/en/problem/sort-integers-ii/
solution:归并排序，注意这里是在原来数组基础上生成了buffer，而不是生成新的数组，注意区别
class Solution:
"""
@param A: an integer array
@return: nothing
"""
def sortIntegers2(self, A):
# write your code here
m = len(A)
temp = [0 for _ in range(m)]
self.mergeSort(A, 0, m - 1, temp)
def mergeSort(self, A, start, end, temp):
if start >= end:
return
mid = (start + end) / 2
#递归，分区间
self.mergeSort(A, start, mid, temp)
self.mergeSort(A, mid + 1, end, temp)
#递归完了以后最后要合并两个"数组"，这里就是两个区间
self.merge(A, start, end, temp)
def merge(self, A, start, end, temp):
mid = (start + end) / 2
left, right = start, mid + 1
# temp buffer已经有了，不能直接append，进行合并一个大区间（不是生成新的数组）
index = start
while left <= mid and right <= end:
if A[left] < A[right]:
temp[index] = A[left]
left += 1
index += 1
else:
temp[index] = A[right]
right += 1
index += 1
while left <= mid:
temp[index] = A[left]
left += 1
index += 1
while right <= end:
temp[index] = A[right]
right += 1
index += 1
for index in range(start, end + 1):
A[index] = temp[index]
solution2: 快排，比归并排序空间复杂度更低，不需要额外的数组，注意pivot的选取
class Solution:
# @param {int[]} A an integer array
# @return nothing
def sortIntegers2(self, A):
# Write your code here
self.quickSort(A, 0, len(A) - 1)
def quickSort(self, A, start, end):
if start >= end:
return
left, right = start, end
# key point 1: pivot is the value, not the index
pivot = A[(start + end) / 2]
# key point 2: every time you compare left & right, it should be
# left <= right not left < right
while left <= right:
while left <= right and A[left] < pivot:
left += 1
while left <= right and A[right] > pivot:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
self.quickSort(A, start, right)
self.quickSort(A, left, end)
网友评论