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和上面的區(qū)別伞芹，不同的函數(shù)
int temp = nums[first];
nums[first] = nums[second];
nums[second] = temp;
}
5.Odd Even Sort
奇數(shù)在前里伯，偶數(shù)在后
public void oddEvenSort(int[] nums) {
int first = 0, second = nums.length-1;
while (first < second) {
while (first < second && nums[fisrt] % 2 == 1) {
first++;//如果是奇數(shù)就跳過繼續(xù)往下遍歷&每次都判斷first < second防止越界
}
while (first < second && nums[second] % 2 == 0) {
second--;
}
if (first < second) {
swap(nums,first++,second--);
}
}
}
6.Pivot Sort
找出一個(gè)數(shù)，左邊的數(shù)都比他小凳枝，右邊的都比他大
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
前后指針，把要?jiǎng)h除的元素放在最后。first指針從左邊開始數(shù)旱易，不相等就跳過，相等就和右邊不等于目標(biāo)值的元素交換
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) {
//等于目標(biāo)值就放在最后
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
//粗暴的做法阀坏，兩個(gè)數(shù)組，兩個(gè)指針分別指向數(shù)組的頭地址笆檀，小的放入新的數(shù)組里忌堂，然后最后再把result的數(shù)壓到nums1里。需要額外空間误债。這道題注意是把nums2壓入nums1浸船，而不是生成一個(gè)新的數(shù)組
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
#比較完以后肯定有一個(gè)數(shù)組沒有出完
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:歸并排序寝蹈，注意這里是在原來數(shù)組基礎(chǔ)上生成了buffer李命，而不是生成新的數(shù)組，注意區(qū)別
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
#遞歸箫老，分區(qū)間
self.mergeSort(A, start, mid, temp)
self.mergeSort(A, mid + 1, end, temp)
#遞歸完了以后最后要合并兩個(gè)"數(shù)組"封字，這里就是兩個(gè)區(qū)間
self.merge(A, start, end, temp)
def merge(self, A, start, end, temp):
mid = (start + end) / 2
left, right = start, mid + 1
# temp buffer已經(jīng)有了，不能直接append耍鬓，進(jìn)行合并一個(gè)大區(qū)間（不是生成新的數(shù)組）
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: 快排阔籽，比歸并排序空間復(fù)雜度更低，不需要額外的數(shù)組牲蜀，注意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)
